%************************************************************************************************
%**    Autor: Maik Funkat																					**
%**																													**
%**    Dieses Dokument steht unter der folgenden Lizenz:									**
%**    Namensnennung-NichtKommerziell-KeineBearbeitung 2.0 Deutschland    	**
%**    			(http://creativecommons.org/licenses/by-nc-nd/2.0/de/)					**
%**																													**
%************************************************************************************************
\documentclass[12pt,a4paper]{scrreprt}

%weitere Packages einbinden
\usepackage[linesnumbered,noline]{algorithm2e}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fancyhdr}
\usepackage{gastex}
\usepackage[utf8x]{inputenc}
\usepackage{mathtools}
\usepackage{ngerman}
\usepackage{ogonek}					%für das Ogonek unter polnischen Namen
\usepackage{pstricks}


%Layout einstellen
\pagestyle{fancy}
\fancyhead[LCR]{}
\renewcommand{\headrulewidth}{0pt}
\fancyfoot[C]{}
\setlength{\parindent}{0cm}


%Theoremstyle einstellen
\newtheoremstyle{diplom}{}{}{}{}{\sffamily\bfseries}{:}{.9em}{}
\theoremstyle{diplom}


%Umgebungen definieren
\newtheorem{satz}{Satz}[chapter]
\newtheorem{defin}[satz]{Definition}
\newtheorem{bsp}[satz]{Beispiel}
\newtheorem{lemma}[satz]{Lemma}
\newtheorem{algo}[satz]{Algorithmus}
\newtheorem*{bsp*}{Beispiel}
\newtheorem*{bew}{Beweis}


% Abkürzungen für Funktionen	
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\val}{\mathrm{val}}
\newcommand{\peek}{\mathrm{peek}}
\newcommand{\pop}{\mathrm{pop}}
\newcommand{\push}{\mathrm{push}}
\newcommand{\tree}{\mathrm{tree}}
\newcommand{\pre}{\mathrm{pre}}
\newcommand{\lab}{\mathrm{label}}
\newcommand{\bl}{\beta_\textsf{L}}
\newcommand{\br}{\beta_\textsf{R}}
\newcommand{\childsize}[1]{|#1|}

% Abkürzungen für Mengen
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Y}{\mathbb{Y}}
\newcommand{\T}{\mathcal{T}}
\newcommand{\dom}{\mathrm{dom}} 


%Abkürzungen für Pfeile
\newcommand{\ra}{\ensuremath{\rightarrow}}
\newcommand{\Ra}{\ensuremath{\Rightarrow}}

	
%Abkürzung für Text und Zeichensymbole
\newcommand{\minus}{\mathbin\backslash}	%	Mengen-Minus
\newcommand{\dcup}{\mathbin{\dot\cup}}	%	disjunkte Vereinigung
\newcommand{\veps}{\varepsilon}


%Abkürzungen für Textformatierung
%\newcommand{\todo}[1]{\footnote{\textbf{ToDo}: #1}}


%Wortsilben
\hyphenation{Teil-ableitungs-baum}
\hyphenation{Ab-leitungs-baum}

%==================================================================================%

\begin{document}
{\sf Universität Leipzig

Fakultät für Mathematik und Informatik

Institut für Informatik}
\vspace{5cm}
\begin{center}
{\sf\large Diplomarbeit}

\

{\sf\Huge Traversierung von komprimierten Wörtern und Bäumen}
\end{center}
\vfill
{\sf\begin{description}
\setlength{\itemindent}{-9pt}
\item 	Leipzig, \today
\item 	\hspace{-10pt}\vspace{-15mm}
			\begin{tabular}{ll}
			Autor:		&	Maik Funkat							\\
							&	Diplom-Informatik				\\
							&	Matrikelnummer: 962 5314	\\
			Betreuer: 	&	Prof. Dr. Markus Lohrey		\\
			\end{tabular}
\end{description}}


\tableofcontents


%==================================================================================%


\fancyfoot[C]{\thepage}
\chapter{Einleitung}
Mit der steigenden Rechen- und Speicherleistung moderner Computer, werden auch die zu verarbeiteten Datenmengen immer größer und komplexer. Dies kann unter Umständen dazu führen, dass Datenmengen zu groß sind. Deshalb ist es notwendig effiziente Kompressionsmethoden zur Verfügung zu haben, um große Mengen an Daten platzsparend zu speichern. Hierzu wurden einige Vorschläge gemacht. 

\

Bei der Entropiekodierung wird die Datenmenge verkleinert indem jedem Zeichen eine unterschiedlich lange Folge von Bits zugeordnet werden. Ein bekanntes Verfahren ist zum Beispiel die Huffman-Kodierung. Hier wird aus den Eingabedaten anhand der Zeichenhäufigkeit ein binärer Baum erzeugt. In seinen Blättern stehen die vorkommenden Zeichen, der Pfad dahin beschreibt die Bitfolge die dem Zeichen zugewiesen wird. Der Baum wird dabei so organisiert, dass keine Bitfolge ein Präfix einer anderen Bitfolge ist (siehe \cite{HuffmanCode}). Ein weiteres Beispiel ist Prediction by Partial Matching (siehe \cite{PaperPPM}), bei dem anhand der bereits gelesenen Zeichen das nächste Zeichen vorhergesagt wird.

\

Ein zweiter Ansatz ist die sogenannte Wörterbuchkompression. Hierbei wird der Text nach mehrmals vorkommenden Zeichenfolgen durchsucht, um sie dann durch eine kürzere Zeichenfolge -- in der Regel ein neues Zeichen -- zu ersetzen. Eines der bekanntesten Beispiele hierbei ist wohl das LZW-Verfahren von Lempel, Ziv und Welch (siehe \cite{LZWelch}, \cite{LZ}). Ein weiteres Beispiel ist das Sequitur-Verfahren von Nevill-Manning und Witten (siehe \cite{Sequitur}). Bei diesem Verfahren wird der Eingabetext eingelesen und zeitgleich komprimiert. Vorgenommene Ersetzungen werden als Regeln in einer kontextfreien Grammatik gespeichert. 

\

Der dritte Ansatz ist die grammatikbasierte Kompression. Eine Grammatik ist hierbei ein Quadrupel bestehend aus einer endlichen Menge von Nichtterminale genannten Symbolen, einer dazu disjunkten, endlichen Menge von Terminalsymbolen, einer Menge von Ableitungsregeln sowie einem ausgewiesenem Startsymbol. Mit Hilfe der Regeln werden vom Startsymbol ausgehend Wörter, also eine Folge von Terminalsymbolen, abgeleitet. Die Menge dieser so erzeugten Wörter nennen wir Sprachen. Wir teilen Grammatiken wiederum, in Abhängigkeit davon welche Formen die Regeln haben dürfen, hierarchisch in Klassen ein. Diese Hierarchie ist unter dem Namen Chomsky-Hierarchie bekannt. Für diese Arbeit von Wichtigkeit ist dabei die Klasse der kontextfreien Grammatiken. Hierbei werden die Regeln so eingeschränkt, dass wir nur noch Nichtterminale ersetzen können. Die kontextfreie Grammatik mit den Regeln $S \ra aSb \mid \veps$ erzeugt beispielweise die Menge aller Wörter $a^nb^n$ für natürliche Zahlen $n$. Bei der Kompression von Wörtern mittels kontextfreier Grammatiken müssen wir also unsere Grammatiken dahingehend einschränken, dass nur genau ein Wort erzeugt wird. Solche Grammatiken nennen wir Straight-Line-Grammatiken. Wir können sie also zur Kompression von Daten benutzen. So haben Larsson und Moffat in \cite{RecursivePairing} ein Recursive-Pairing-Verfahren, kurz \textsc{RePair}, vorgeschlagen. Hierbei wird die Häufigkeit aller aufeinanderfolgenden Symbole $ab$ des Strings $w$, Digramme genannt, ermittelt. Die Vorkommen des am häufigsten vorkommenden Digramm wird durch ein neues Symbol $A$ ersetzt und wir merken uns die Ersetzung als Regel $A \ra ab$. Das RePair-Verfahren bildet auch die Grundlage für die später verwendeten Straight-Line-Grammatiken.

\

Neben einer effizienten Komprimierung benötigen wir aber auch Algorithmen um mit diesen Daten arbeiten zu können. Eine wichtige Problemstellung ist zum Beispiel das Pattern Matching. Hierbei sollen alle Vorkommnisse eines Muster $u$ in einem längeren Wort $v$ ermittelt werden. Üblicherweise bedeutet dies eine komplette Dekompression der Daten. Dies kann insbesondere bei sehr großen Datenmengen jedoch leicht zu Speicherplatzproblemen führen. Deshalb ist es sinnvoll Algorithmen zu entwerfen, die auf den komprimierten Daten arbeiten und so keine komplette Dekompression benötigen. Dazu wurden bereits einige Ansätze vorgestellt. Für die Laufzeitlängenkodierung schlugen Amir, Landau und Farrach in \cite{RunLength} einen Pattern-Matching-Algorithmus vor der in linearer Zeit und linearem Platz arbeitet. Für LZW-komprimierte Daten haben Amir, Benson und Farrach in \cite{CompressedSearchLZW} Algorithmen vorgestellt mit denen man das erste Vorkommen eines Musters der Länge $m$ in einem komprimierten Text der Länge $n$ in Zeit $O(n + m^2)$ oder $O(n \log m + m)$ finden kann. G\k{a}sieniec, Kolpakov, Potapov und Sant haben in \cite{RTGrammarComp} untersucht wie man aufeinanderfolgende Symbole aus grammatikbasierten komprimierten Dateien wiederherstellt. Sie konnten dabei zeigen, dass man aus einer Straight-Line-Grammatik $G = (N, P, S)$ mit nur $O(|P|^2)$ extra Platz in konstanter Zeit das nachfolgende Symbol erhalten kann. 

\

Wir werden im Rahmen dieser Arbeit diesen Algorithmus implementieren. Außerdem werden wir die Datenstrukturen so erweitern, dass wir beliebig im Text vorwärts und rückwärts navigieren können. Desweiteren werden wir diese Resultate auf Bäume und Baumgrammatiken verallgemeinern. Für einen Überblick über dieses Themengebiet bieten sich \cite{TaTa} und \cite{GeneralTrees} an. Wir werden in dieser Arbeit nur endliche, knotenbeschriftete Bäume über einem Rangalphabet betrachten. Mit Hilfe von Baumgrammatiken können wir Mengen von Bäumen erzeugen, auch Baumsprachen genannt. Analog zu den Wörtern werden wir Straight-Line-Baumgrammatiken definieren die genau einen Baum erzeugen. Damit können wir sie zur Kompression von Bäumen benutzen. Beispiele für Algorithmen hierfür sind BPLEX (siehe \cite{BPLEX}) und TreeRePair (siehe \cite{TreeRePairPaper} und \cite{TreeRePairImpl}).

\

Die Rest der Arbeit ist wie nachfolgend erklärt aufgebaut. Zuerst werden wir uns einige formale Grundlagen in unser Gedächtnis rufen. Dazu gehören Definitionen für kontextfreie Wortgrammatiken und Ableitungsbäume. Außerdem werden wir im zweiten Kapitel Straight-Line-Grammatiken definieren. Wir werden das Ergebnis von G\k{a}sieniec, Kolpakov, Potapov und Sant erwähnen und zeigen, dass mit $O(|P|^2)$ weiteren Platz auch eine beliebige Navigation im Text in konstanter Zeit pro Symbol möglich ist. Im dritten Kapitel werden wir Baumgrammatiken und insbesondere Straight-Line-Baumgrammatiken vorstellen. Wir werden zeigen, dass diese eine Verallgemeinerung von Wortgrammatiken darstellen. Dann werden wir im vierten Kapitel die für Wortgrammatiken geltenden Resultate auf  Baumgrammatiken erweitern. Im fünften Kapitel werden wir abschließend ein paar zusätzliche Resultate sowie Erweiterungen besprechen.

%==================================================================================%


\chapter{Grundlagen}
In der Informatik sind formale Sprachen über einem endlichen Alphabet $\Sigma$ ein wichtiges Konzept. Wir können sie automatentechnisch behandeln oder prädikatenlogisch erfassen. In dieser Arbeit werden wir das Konzept der Grammatiken verwenden, um unsere Resultate zu zeigen. Zuerst werden wir uns einige Grundlagen die wir zum weiteren Verständnis benötigen definieren.

\section{Grammatiken}
Mit $\N = \{0, 1, 2, \ldots\}$ bezeichnen wir die Menge der natürlichen Zahlen. Für eine beliebige Menge $M$ bezeichnen wir mit $M^*$ die Menge aller endlichen Wörter über $M$ und insbesondere mit $\veps$ das leere Wort. Mit $\cdot$ meinen wir die Konkatenation von Wörtern.

\begin{defin}
Sei $\Sigma$ eine endliche Menge. Eine \emph{kontextfreie} (\emph{Wort-})\emph{Grammatik} (über $\Sigma$) ist ein Tripel $G = (N, P, S)$ wobei 
\begin{itemize}
	\item $N$ eine endliche Menge mit $\Sigma \cap N = \emptyset$ ist,
	\item $P \subseteq N \times (N \cup \Sigma)^*$ eine Menge von
	Regeln ist und
	\item $S \in N$ das Startsymbol ist.
\end{itemize}
Die Elemente von $\Sigma$ nennen wir Terminalsymbole, die Elemente von $N$ bezeichnen wir als Nichtterminalsymbole. Meist reicht es statt der gesamten Grammatik nur die Regeln anzugeben, da aus diesen $N, S$ sowie $\Sigma$ ersichtlich werden. Eine Regel $(A, \alpha) \in P$ schreiben wir zum leichteren Verständnis auch in der Form $A \ra \alpha$. Um aus Grammatiken Wörter zu erzeugen, müssen wir diese aus dem Startsymbol unter Benutzung der Regeln ableiten. Wir können $u \in (\Sigma \cup N)^*$ nach $v \in (\Sigma \cup N)^*$ \emph{ableiten}, kurz $u \Ra_G v$, wenn es eine Regel $(A \ra \alpha) \in P$ und Wörter $u',u'',v',v'' \in (\Sigma \cup N)^*$ gibt, so dass $u = u'Au''$ und $v = v'\alpha v''$ gilt. Wir nennen $\Ra_G$ die \emph{Ableitungsrelation} von $G$ und mit $\Ra_G^*$ bezeichnen wir den reflexiv transitiven Abschluss von $\Ra_G$. Die \emph{Sprache} von $G$ ist dann definiert als die Menge $L(G) := \{w \in \Sigma^* \mid S \Ra_G^* w\}$.
\end{defin}

\begin{bsp}\label{bsp:cfGrammar}
Sei $\Sigma = \{a, c\}$ und $G$ durch die Regeln $S \ra aSa \mid cSc \mid aa \mid cc$ gegeben. Dann ist $L(G) = \{w \in \Sigma^* \mid w = u_1 \ldots u_{n+1} u_{n+1} \ldots u_1$ mit $u_i \in \Sigma $ für alle $1 \leq i \leq n+1\}$, also die Menge aller echten Palindrome gerader Länge über $\Sigma$.
\end{bsp}

Es ist ein allgemein bekannter Fakt, dass wir jede kontextfreie Grammatik in die sogenannte Chomsky-Normalform bringen können. Dies ist später auch bei der Umsetzung des Algorithmus für Straight-Line-Grammatiken hilfreich.

\begin{defin}
Sei $G = (N, P, S)$ eine kontextfreie Grammatik. Sie ist in \emph{Chomsky-Normalform}, oder kurz CNF, wenn alle  Regeln die Form $A \ra a$ oder $A \ra BC$ haben für $A, B, C \in N$ und $a \in \Sigma$.
\end{defin}

\begin{satz}\label{satz:wordCNF}
Sei $G = (N, P, S)$ eine kontextfreie Grammatik. Dann existiert eine Grammatik $G'$ in CNF mit $L(G) = L(G')$.
	\end{satz}

Den Beweis hierfür lassen wir aus, da er für das weitere Verständnis der Arbeit unwichtig ist. Er kann jedoch an geeigneter Stelle nachgelesen werden, z.\,B. in \cite{CNF}.

\begin{defin}
Sei $G = (N, P, S)$ eine kontextfreie Grammatik und $w \in L(G)$. Ein \emph{Ableitungsbaum} von $w$ ist ein planarer, beschrifteter Baum mit einer endlichen, nicht-leeren Knotenmenge $V_G \subseteq \N^*$ für den gilt:
\begin{itemize}
	\item Die Wurzel $\veps$ ist mit $S$ beschriftet.
	\item Jeder innere Knoten ist mit einem Symbol aus $N$ und jedes Blatt ist mit einem Symbol aus $\Sigma$ beschriftet.
	\item Ist ein Knoten $v \in V_G$ mit $A \in N$ beschriftet und gibt es eine Regel $A \ra A_1 \ldots A_n$, so existieren Knoten $v.1, \ldots, v.n \in V_G$ die mit $A_1$ bis $A_n$ beschriftet sind sowie Kanten von $v$ zu $v.j$ für $1 \leq j \leq n$.
	\item $w$ ist die Konkatenation der Blattbeschriftungen von links nach rechts gelesen.
\end{itemize}
Wir bezeichnen den Ableitungsbaum von $w$ auch kurz mit $\tree_G(w)$. Seien jetzt $u, v \in V_G$ Knoten des Ableitungsbaumes. Der \emph{kleinste gemeinsame Vorfahre} (LCA) von $u$ und $v$ ist der Knoten $x \in V_G$, so dass $u = x.i$ und $v = x.j$ für geeignete $i, j \in \N^*$ gilt.
\end{defin}

Es ist leicht ersichtlich, dass wenn $x$ der LCA zweier Knoten $u$ und $v$ ist, er auch der LCA von $u$ und allen Nachfahren des Knoten $v$ ist. Anhand des Beispiels \ref{bsp:cfGrammar} haben wir gesehen, dass kontextfreie Grammatiken unendlich viele Wörter erzeugen können. Da wir bei der Komprimierung von Texten durch Grammatiken jedoch stets dasselbe Wort erhalten wollen, müssen wir unsere Grammatiken so einschränken, dass diese genau ein Wort erzeugen. Dafür nutzen wir Straight-Line-Grammatiken.

\begin{defin}
Eine kontextfreie Grammatik $G = (N, P, S)$ nennen wir \emph{Straight-Line-Grammatik} wenn zusätzlich gilt:
\begin{enumerate}
\item Für jedes Nichtterminal $A \in N$ gibt es genau eine Regel $(A \ra w_A)$ in $P$.
\item Die Relation $\{(A, B) \in N \times N \mid B$ kommt in $w_A$ vor$\}$ ist azyklisch.
\end{enumerate}
\end{defin}

Die Azyklizität stellt sicher, dass jede Straight-Line-Grammatik $G$ genau ein Wort produziert. Dieses Wort nennen wir $\val(G)$. Dementsprechend meinen wir abkürzend mit dem Ableitungsbaum von $G$ den Ableitungsbaum des Wortes $\val(G)$. Wir nennen zudem den vom Nichtterminal $A$ mittels der Regeln aus $P$ so erzeugten Teilableitungsbaum $\tree_G(A)$. Um Straight-Line-Grammatiken besser zu verstehen, wollen wir uns zwei Beispiele ansehen.

\newpage\begin{bsp}\label{bsp:slcfGrammar}
Betrachte die folgenden Beispiele:
\begin{enumerate}
\item Die Straight-Line-Grammatik $G$ sei durch folgende Regeln definiert:
\[\begin{array}{lllll}
		\vspace{4pt}A \ra ab	&	B \ra Ab	&	C \ra BA	&	D \ra CB	&	E \ra DC	\\
		\vspace{4pt}F \ra ED	&	G \ra FD	&	H \ra GB	&	I \ra Ha
	\end{array}	\]
Dann ist $\val(G) = abbababbabbababbababbabbababbabba$.

\item Die Straight-Line-Grammatik $G_n$ enthalte die Regeln $A_i \ra A_{i+1}A_{i+1}$ und $A_n \ra ac$ mit $0 \leq i < n$. Wir sehen leicht, dass $\val(G_n) = (ac)^{2^n}$ ist. Abbildung \ref{fig:slpDerivTree} zeigt uns den Ableitungsbaum von $G_n$.\end{enumerate}
\end{bsp}

\begin{figure}[h]
\begin{center}
\begin{picture}(100,20)(0,-20)
\gasset{Nframe=n,Nw=6,Nh=6,AHnb=0,Nmr=0}
\node(A0)(50,0){$A_0$}
\node(A1L)(30,-5){$A_1$}
\node(A1Lvdots)(20,-10){\rput{27}(0,0){...}}
\node[Nw=7](An-1L)(10,-15){$A_{n-1}$}
\node(AnLL)(0,-20){$A_n$}
\node(AnLLa)(-3,-25){$a$}
\node(AnLLc)(3,-25){$c$}
\node(AnLR)(20,-20){$A_n$}
\node(AnLRa)(17,-25){$a$}
\node(AnLRc)(23,-25){$c$}
\node(A1Ldots)(40,-10){\rput{333}(0,0){...}}

\node(A1R)(70,-5){$A_1$}
\node(A1Rdots)(60,-10){\rput{27}(0,0){...}}
\node(A1Rvdots)(80,-10){\rput{333}(0,0){...}}
\node[Nw=7](An-1R)(90,-15){$A_{n-1}$}
\node(AnRL)(80,-20){$A_n$}
\node(AnRLa)(77,-25){$a$}
\node(AnRLc)(83,-25){$c$}
\node(AnRR)(100,-20){$A_n$}
\node(AnRRa)(97,-25){$a$}
\node(AnRRc)(103,-25){$c$}

\drawedge(A0,A1L){}
\drawedge(A1L,A1Lvdots){}
\drawedge(A1Lvdots,An-1L){}
\drawedge(An-1L,AnLL){}
\drawedge(AnLL,AnLLa){}
\drawedge(AnLL,AnLLc){}
\drawedge(An-1L,AnLR){}
\drawedge(AnLR,AnLRa){}
\drawedge(AnLR,AnLRc){}
\drawedge(A1L,A1Ldots){}

\drawedge(A0,A1R){}
\drawedge(A1R,A1Rdots){}
\drawedge(A1R,A1Rvdots){}
\drawedge(A1Rvdots,An-1R){}
\drawedge(An-1R,AnRL){}
\drawedge(AnRL,AnRLa){}
\drawedge(AnRL,AnRLc){}
\drawedge(An-1R,AnRR){}
\drawedge(AnRR,AnRRa){}
\drawedge(AnRR,AnRRc){}
\end{picture}
\end{center}
\caption{Ableitungsbaum von $G_n$}
\label{fig:slpDerivTree}
\end{figure}

Das zweite Beispiel zeigt uns, dass wir aus Straight-Line-Grammatiken mit $n+1$ Regeln exponentiell lange Texte erzeugen können. Dadurch erhalten wir jedoch auch Ab\-leitungs\-bäume mit exponentiell vielen, hier $2^{n + 2} - 1$, Knoten. Wir würden somit exponentiell viel Speicherplatz benötigen. Es steht also außer Frage, dass eine komplette Berechnung des Ableitungsbaumes zu teuer wäre.

\section{Traversierung und Navigation}
Sei $G = (N, P, S)$ eine Straight-Line-Grammatik über $\Sigma$. G\k{a}sieniec et.\,al. haben in \cite{RTGrammarComp} einen Algorithmus vorgestellt mit dem wir den Wert von $\val(G)$ aus dem komprimierten Text sukzessive in Zeit $O(1)$ pro Symbol und Platz $O(|P|^2)$ wiederherstellen können ohne diesen komplett zu dekomprimieren oder den gesamten Ableitungsbaum berechnen zu müssen. Wir werden die formalen Grundlagen schaffen und dann den Algorithmus vorstellen. Außerdem werden wir den Algorithmus erweitern und erhalten damit die Möglichkeit im Wort beliebig nach links und rechts zu navigieren. Dies können wir ebenfalls in konstanter Zeit pro Symbol und Platz $O(|P|^2)$.

\

Um Straight-Line-Grammatiken zu erzeugen, verwenden wir den Re\-cur\-sive-Pair\-ing-Al\-go\-rith\-mus \textsc{RePair} von Larsson und Moffat (siehe \cite{RecursivePairing}). Wir erhalten dabei nur Regeln der Form $A \ra BC$ mit $A, B, C \in N \cup \Sigma$. Dies stellt keine Einschränkung dar, da wir jede kontextfreie Grammatik zuerst in Chomsky-Normalform bringen können und anschließend für alle Regeln $A \ra a$ jedes auf einer rechten Seite vorkommende $A$ durch $a$ ersetzen. Wir nennen zudem auch $B$ linkes und $C$ rechtes Kind von $A$.

\

Im Algorithmus werden wir mit dem Ableitungsbaum von $G$ arbeiten. Wir werden diesen jedoch nicht berechnen, sondern drei vorberechnete Abbildungen benutzen um einzelne Knoten zu kodieren. Unterstützend verwenden wir dazu einen Stack. Sei also für den Rest des Kapitels $G = (N, P, S)$ eine beliebige, feste Straight-Line-Grammatik. Sprechen wir vom Ableitungsbaum, so meinen wir den Ableitungsbaum von $G$.

\begin{defin}
Sei $A \in N$ ein beliebiges Nichtterminal. Per Definition gibt es genau eine Regel $(A \ra A_1A_2) \in P$. Die \emph{Linksableitung} von $A$ ist das Symbol $A_1$. Wir definieren die Folge der Linksableitungen $L : N \ra N^* \cdot \Sigma$ induktiv durch:
\[ L(A) =
\begin{cases}
	A_1 \cdot L(A_1)		&	\textrm{falls } A_1 \in N \\
	A_1							&	\textrm{falls } A_1 \in \Sigma	\\ 
\end{cases}
\]
Sei nun $L(A) = [A_1, \ldots, A_n]$. Die Länge $H : N \ra \N$ einer Ableitungsfolge definieren wir mit  $H(A) = n$. Wir definieren außerdem $L_i(A)$ für $1 \leq i \leq H(A)$ als das $i$-te Symbol der Folge $L(A)$.
\end{defin}

Das erste Symbol von $\val(G)$ ist die Beschriftung des am weitesten links liegenden Knoten im Ableitungsbaum von $G$. Dies entspricht der maximalen Linksableitung, also hat es den Wert $L_{H(S)}(S)$. Für die Abbildung $L$ müssen wir für jedes Nichtterminal $A$ eine Ableitungsfolge speichern. Die Länge dieser Folgen ist aufgrund der Definition von Straight-Line-Grammatiken beschränkt durch die Anzahl der Nichtterminale. Somit benötigen wir zum Speichern der Abbildung $L$ den Platz $O(|P|^2)$.

\begin{bsp}
Nehmen wir erneut die Grammatiken $G_n$ aus Beispiel \ref{bsp:slcfGrammar}.2. Anhand der Definitionen für Linksableitungen lassen sich so folgende Aussagen treffen:
\begin{itemize}
\item $L(A_j) = [A_{j+1}, \ldots, A_n, a]$ für $0 \leq j \leq n$
\item $L_{H(A_0)}(A_0) = \ldots = L_{H(A_n)}(A_n) = a$ 
\item $H(A_j) = n-j+1$
\end{itemize}
\end{bsp}

Wie bereits erwähnt benutzen wir im Algorithmus einen Stack von Paaren $\langle F, i\rangle$, um Knoten im Ableitungsbaum zu kodieren. Dazu benötigen wir eine Definition eines Stacks.

\begin{defin}
Sei $M$ eine Menge. Ein \emph{Stack} über $M$ ist ein Tupel $T = [t_1, \ldots, t_n]$ mit $t_i \in M$ für $1 \leq i \leq n$. Sei außerdem $M_{st}$ die Menge aller Stacks über $M$. Um mit den Stacks arbeiten zu können, benötigen wir Operationen, um das oberste Element zu erhalten (peek), Elemente vom Stack zu holen (pop), neue Elemente hinzuzufügen (push) sowie die Größe des Stacks zu berechnen.
\begin{itemize}
\item $\peek : M_{st} \ra M :  [t_1, \ldots, t_n] \mapsto t_n$
\item $\pop : M_{st} \ra M_{st} : [t_1, \ldots, t_{n-1}, t_n] \mapsto [t_1, \ldots, t_{n-1}]$
\newpage\item $\push : M_{st} \times M \ra M_{st} : ([t_1, \ldots, t_n], t') \mapsto [t_1,  \ldots, t_n, t']$
\item $|\cdot| : M_{st} \ra \N : [t_1, \ldots, t_n] \mapsto n$
\end{itemize}
Wir nennen $\peek(T)$ auch den Top-Stack.
\end{defin}

\section{Wiederherstellung des Textes}
Wir haben jetzt alle Voraussetzungen geschaffen und können den Algorithmus angeben. Sei $T = [t_1, \ldots, t_n]$ ein Stack über $N \times \N$ mit $t_j = \langle F_j, i_j\rangle$ für $1 \leq j \leq n$. Wir verwenden ihn um Knoten im Ableitungsbaum zu kodieren. Wenn im Algorithmus $\langle F, i\rangle = \pop(T)$ steht, so meinen wir: speichere zuerst den Top-Stack in $\langle F, i\rangle$ und führe dann $\pop(T)$ aus.

\begin{algo}[Linkstraversierung]\label{algo:wordTraverse}\

Eingabe: Straight-Line-Grammatik $G = (N, P, S)$ über $\Sigma$

Ausgabe: $\val(G)$

\begin{algorithm}[H]
\DontPrintSemicolon

\BlankLine
\textbf{report} $L_{H(S)}(S)$\;
$\push(T, \langle S, H(S)\rangle)$\;
\Repeat{$|T| = 0$}{
	$\langle F, i\rangle = \pop(T)$\;
	\eIf{$i > 1$}{
		$\push(T, \langle F, i-1\rangle)$\;
		$Q = L_{i-1}(F)$
	}{
		$Q = F$
	}
	\;
	$Q_{\mathrm{right}} = $ rechtes Kind von $Q$\;
	\eIf{$Q_{\mathrm{right}} \in \Sigma$}{
		\textbf{report} $Q_{\mathrm{right}}$
	}{
		\textbf{report} $L_{H(Q_{\mathrm{right}})}(Q_{\mathrm{right}})$\;
		$\push(T, \langle Q_{\mathrm{right}}, H(Q_{\mathrm{right}})\rangle)$
	}  
}
\end{algorithm}
\end{algo}

\begin{satz}
Es gibt einen Algorithmus der einen durch eine Straight-Line-Grammatik komprimierten Text in Zeit $O(1)$ pro Symbol und mit Platz $O(|P|^2)$ wiederherstellt.
\end{satz}

\begin{bew}
Algorithmus \ref{algo:wordTraverse} gibt zuerst das am weitesten links stehende Symbol $L_{H(S)}(S)$ als erstes Symbol aus und speichert die Position $\langle S, H(S)\rangle$ des ersten Blattes im Ab\-leitungs\-baum im Stack ab. Anschließend arbeitet er den Stack in einer Schleife ab. Sei also $\langle F, i\rangle$ das aktuelle vom Stack geholte Element. Der aktuelle Knoten $u_{\ell} = u_1.\,...\,.u_{n-1}.1$ mit $u_1, \ldots, u_{n-1} \in \N$ ist mit $L_i(F)$ beschriftet. Um das nächste Textsymbol zu erhalten, müssen wir den kleinsten gemeinsamen Vorfahren von $u_{\ell}$ und dem nächsten, noch unbekannten, Blatt berechnen.
Ist $i > 1$, so haben wir eine Kette von Linksableitungen und finden den LCA in $Q := L_{i-1}(F)$. Ansonsten ist $Q := F$ selbst der LCA. In beiden Fällen gehört zu $Q$ der Knoten $u = u_1.\,...\,.u_{n-1}$.
Das nächste Textsymbol finden wir beim rechten Kind von $Q$, dem mit $Q_{\mathrm{right}}$ beschrifteten Knoten $u_r = u_1.u_2.\,...\,.u_{n-1}.2$. Damit ist $u$ der LCA von $u_{\ell}$ und $u_r$.  Ist $Q_{\mathrm{right}}$ ein Terminalsymbol, so haben wir unser nächstes Textsymbol gefunden. Andernfalls wird von $Q_{\mathrm{right}}$ der Teilableitungsbaum $\tree_G(Q_{\mathrm{right}})$ aufgespannt. Natürlich ist $u$ auch der LCA aller Knoten dieses Teilableitungsbaumes. Das nächste Textsymbol ist nun das erste Symbol dieses Baumes, also $L_{H(Q_{\mathrm{right}})}(Q_{\mathrm{right}})$. Da $\tree_G(Q_{\mathrm{right}})$ mehr als ein Blatt hat, müssen wir ihn mit Hilfe des Stacks ebenfalls abarbeiten, d.\,h. wir fügen $\langle Q_{\mathrm{right}}, H(Q_{\mathrm{right}})\rangle$ zum Stack hinzu. In jedem Schleifendurchlauf müssen wir nur konstante viele Befehle ausführen um das nächste Symbol auszugeben. Damit liegt die Laufzeit bei $O(1)$ pro Symbol. Der Algorithmus terminiert schließlich, wenn wir das am weitesten rechts liegende Symbol gefunden haben.\hfill$\Box$
\end{bew}

Um den Algorithmus leichter verständlich zu machen, schauen wir uns eine kurze Beispielrechnung an.

\begin{bsp}\label{bsp:wordAlgoExRun}
Sei $G$ die Grammatik aus Beispiel \ref{bsp:slcfGrammar}.1. Wenden wir den Algorithmus auf diese Grammatik an, so erhalten wir $abbababbabbababbababbabbababbabba$ als Endausgabe. Exemplarisch sei hier die Berechnung innerhalb der Schleife für den Stack $T = [\langle I, 7\rangle]$ gezeigt.

\begin{itemize}
\item 	$\langle F, i\rangle = \pop(T) = \langle I, 7\rangle$
\item 	Da $7 > 1 \Rightarrow T = [\langle I, 6\rangle], Q = L_6(I) = C$
\item 	rechtes Kind von $C$ ist $Q_{\mathrm{right}} = A$
\item 	Da $A_1 \not\in \Sigma \Rightarrow$ report $L_{H(A)}(A) = L_1(A) = a, T = [\langle I,6\rangle, \langle A, 1\rangle]$
\end{itemize}

Der nächste Schleifendurchlauf wäre dann
\begin{itemize}
\item 	$\langle F, i\rangle = \langle A, 1\rangle$
\item 	Da $1 \not> 1 \Rightarrow Q = A$
\item 	rechtes Kind von $A$ ist $Q_{\mathrm{right}} = b$
\item 	Da $b \in \Sigma \Rightarrow$ report $b$
\end{itemize}
\end{bsp}

\section{Navigation im Text}
Durch eine kleine Erweiterung des theoretischen Konstruktes können wir auch eine beliebige Navigation im Text ermöglichen. Mit den Linksableitungen konnten wir das am weitesten links stehende Symbol des aus einem Nichtterminal erzeugten Ableitungsbaum erhalten. Genauso erreichen wir dies für das am weitesten rechts stehende Symbol, indem wir Rechtsableitungen benutzen. Die Definition erfolgt auf analoge Art und Weise. Es ist somit leicht zu sehen, dass auch die Abbildung $R$ den Platz $O(|P|^2)$ zum abspeichern benötigt. Die Zeit- und Platzkomplexität des Navigationalgorithmus ist dann dieselbe wie im Traversierungsalgorithmus.

\begin{defin}
Sei $A \in N$ ein beliebiges Nichtterminal und $(A \ra A_1A_2) \in P$ die dazugehörige Regel. Die \emph{Rechtsableitung} von $A$ ist das Symbol $A_2$. Wir definieren die Folge der Rechtsableitungen $R : N \ra N^* \cdot \Sigma$ induktiv wie folgt:
\[ R(A) =
\begin{cases}
	A_2 \cdot R(A_2)		&	\textrm{falls } A_2 \in N \\
	A_2							&	\textrm{falls } A_2 \in \Sigma	\\ 
\end{cases}
\]
Sei nun $R(A) = [A_1, \ldots, A_n]$. Die Länge $W : N \ra \N$ einer Ableitungsfolge definieren wir mit $W(A) = n$. Wir definieren außerdem $R_i(A)$ als das $i$-te Symbol der Folge $R(A)$ für $1 \leq i \leq W(A)$.
\end{defin}

Wie im Traversierungsalgorithmus wollen wir wieder einen Stack als Hilfsstruktur benutzen um Knoten im Ableitungsbaum zu kodieren. Da wir jetzt jedoch zwischen Links- und Rechtsableitungen unterscheiden, können wir nicht denselben Stack verwenden. Sei deshalb $T$ ein Stack über $N \times \N \times \{L, R\}$. Der Tupel $\langle X, i, d\rangle$ bedeutet dabei: Gehe im Ableitungsbaum vom Nichtterminal $X$ genau $i$ Schritte in Richtung $d$. Ist $d = L$, so nennen wir solche Tupel auch Linksketten. Analog bezeichnen wir sie für $d = R$ als Rechtsketten. 

\

Außerdem müssen wir für den Stack noch ein paar Forderungen formulieren um ungültige Kodierungen zu verhindern. Sei also $T = [t_1, \ldots, t_n]$ ein Stack mit $t_j = \langle X_j, i_j, d_j\rangle$ für $1 \leq j \leq n$. Dann müssen nachfolgende Punkte stets erfüllt sein:
{\renewcommand{\labelenumi}{(\roman{enumi})}
\begin{enumerate}
\item 	$X_1 = S$
\item 	$d_j = L \Leftrightarrow d_{j+1} = R$ für $1 \leq j < n$
\item 	Der Stack beschreibt immer einen Pfad von der mit $S$ beschrifteten Wurzel hin zu einem mit $L_{i_n}(X_n)$ bzw.\, $R_{i_n}(X_n)$ beschriftetem Blattknoten.
\end{enumerate}}

Wir wollen im Text die Möglichkeit haben sowohl vorwärts, also nach rechts, als auch rückwärts, also nach links, zu gehen. Dazu müssen wir anhand des aktuellen Stacks entscheiden. Jeder Schritt in eine Richtung führt zu einer Veränderung des Stacks. Um den nächsten Blattknoten zu finden, müssen wir zuerst den LCA $X_v$ von diesem Knoten und dem aktuellen Blattknoten berechnen.

\subsection{Rechtsschritt}
Wir betrachten die Richtungsanweisung des Top-Stacks $t_n = \langle X_n, i_n, d_n\rangle$. Diese kann laut Definition zwei mögliche Werte haben. Im Falle von $d_n = L$ müssen wir drei Unterfälle unterscheiden.

\

Fall $i_n = 1, X_n = S$: Die Linkskette der Länge 1 beginnt an der Wurzel des Ableitungsbaumes. Der LCA ist also $S$. Zu $S$ gehört eine Regel $S \ra aX_2$. Das nächste Textsymbol ist also das erste Symbol von $X_2$. Wir gehen im Ableitungsbaum also einen Schritt nach rechts. Wir ersetzen $t_n$ durch $\langle S, 1, R\rangle$. Ist $X_2 = R_1(S) \in \Sigma$, so haben wir das nächste Textsymbol bereits gefunden. Andernfalls ist es das am weitesten links stehende Symbol von $\tree_G(X_2)$. Wir fügen in diesem Fall noch $\langle X_2, H(X_2), L\rangle$ zum Stack hinzu. Abbildung \ref{fig:txtRNaviSiL} zeigt dies auch noch einmal bildlich.

\begin{figure}[h]
\begin{center}
\begin{picture}(28,20)(0,-18)
\gasset{Nframe=n,AHnb=0,Nw=6,Nh=6}
\node(nS)(10,0){$S$}
\node[Nw=5,Nh=5](nL)(0,-10){$a$}
\node(nX2)(20,-10){$X_2$}
\node[NLdist=-2.5,Nw=0](ndl)(12,-20){$a$}
\node[Nw=0](ndr)(28,-20){}
\drawedge[ELside=r](nS,nL){\small 1}
\drawedge(nS,nX2){\small 1}
\drawedge[sxo=2.7](nX2,ndl){}
\drawedge[sxo=-4.1](nX2,ndr){}
\drawedge(ndl,ndr){}
\end{picture}
\end{center}
\caption{Fall $d_n = L, i_n = 1, X_n = S$}
\label{fig:txtRNaviSiL}
\end{figure}

Fall $i_n = 1, X_n \not= S$: Wir entfernen den Top-Stack. Da $X_n \not= S$, muss $n > 1$ gelten. Der Stack ist also nicht leer.  Aufgrund von (ii) muss nun $t_{n-1}$ eine Rechtskette sein. Der LCA ist somit der Knoten $X_n$ selbst. Da $X_n$ ein Nichtterminal ist, gibt es eine Regel $X_n \ra aX_n'$. Weil zudem $R_{i_{n-1}}(X_{n-1}) = X_n$ ist, können wir die Rechtskette von $t_{n-1}$ um einen weiteren Schritt verlängern. Wir erreichen den Knoten $X_n' = R_k(X_{n-1})$ mit $k = i_{n-1}+1$. Wir ersetzen somit $t_{n-1}$ durch $\langle X_{n-1}, k, R\rangle$. Ist $X_n' \in \Sigma$, so haben wir das nächste Textsymbol gefunden. Andernfalls wird wie im vorangegangenen Fall ein Teilableitungsbaum $\tree_G(X_n')$ aufgespannt und wir finden den nächsten Blattknoten im am weitesten links stehenden Knoten. Wir fügen in diesem Fall $\langle X_n', H(X_n'), L\rangle$ zum Stack hinzu. Abbildung \ref{fig:wordNaviLi1nS} zeigt den Fall noch einmal bildlich.

\begin{figure}[h]
\begin{center}
\begin{picture}(38,43)(0,-41)
\gasset{Nframe=n,AHnb=0,Nw=6,Nh=6}
\node(nX1)(13,0){\rput{45}(0,0){...}}
\node(nXn-1)(5,-8){$X_{n-1}$}
\node(nXn-1l)(-3,-16){\rput{45}(0,0){...}}
\node(nXv)(20,-23){$X_n$}
\node[Nw=5,Nh=5](na)(10,-33){$a$}
\node(nXns)(30,-33){$X_n'$}
\node[NLdist=-2.5,Nw=0](ndl)(22,-43){$a$}
\node[Nw=0](ndr)(38,-43){}

\drawedge(nX1,nXn-1){}
\drawedge(nXn-1,nXn-1l){}
\drawedge[ELpos=60](nXn-1,nXv){\small$i_{n-1}$}
\drawedge[ELside=r](nXv,na){\small 1}
\drawedge(nXv,nXns){\small 1}
\drawedge[sxo=2.7](nXns,ndl){}
\drawedge[sxo=-4.1](nXns,ndr){}
\drawedge(ndl,ndr){}
\end{picture}
\end{center}
\caption{Fall $d_n = L, i_n = 1, X_n \not= S$}
\label{fig:wordNaviLi1nS}
\end{figure}

Fall $i_n > 1$: Wir haben eine Linkskette mit mehr als einem Schritt. Den LCA erhalten wir indem wir einen Schritt weniger nach links gehen, also $X_v = L_{i_n-1}(X_n)$. Zu $X_v$ gehört eine Regel $X_v \ra aX_n'$. Um also das nächste Textsymbol zu erhalten, müssen wir einen Schritt nach rechts zu $X_n' = R_1(X_v)$ gehen. Wir ersetzen den Top-Stack $t_n$ durch $\langle X_n, i_n - 1, L\rangle$ und fügen $\langle X_v, 1, R\rangle$ zum Stack hinzu. Ist $X_n' \in \Sigma$, so haben wir das nächste Textsymbol gefunden. Andernfalls spannt wieder $X_n'$ den Teilableitungsbaum $\tree_G(X_n')$ auf und das nächste Textsymbol ist das am weitesten links stehende Symbol von diesem. Wir fügen noch $\langle X_n', H(X_n'), L\rangle$ zum Stack hinzu. Abbildung \ref{fig:wordNaviLig1} zeigt diesen Fall zudem bildlich.

\begin{figure}[h]
\begin{center}
\begin{picture}(28, 41)(0,-39)
\gasset{Nframe=n,AHnb=0,Nw=6,Nh=6}
\node(nX1)(16,0){\rput{325}(0,0){...}}
\node[Nw=7](nXn)(25,-6){$X_n$}
\node(nXnr)(34,-12){\rput{325}(0,0){...}}
\node(nXv)(10,-21){$X_v$}
\node[Nw=5,Nh=5](na)(0,-31){$a$}
\node(nXns)(20,-31){$X_n'$}
\node[NLdist=-2.5,Nw=0](ndl)(12,-41){$a$}
\node[Nw=0](ndr)(28,-41){}

\drawedge(nX1,nXn){}
\drawedge(nXn,nXnr){}
\drawedge[ELside=r,ELpos=65](nXn,nXv){\small$i_n-1$}
\drawedge[ELside=r](nXv,na){\small 1}
\drawedge(nXv,nXns){\small 1}
\drawedge[sxo=2.7](nXns,ndl){}
\drawedge[sxo=-4.1](nXns,ndr){}
\drawedge(ndl,ndr){}
\end{picture}
\end{center}
\caption{Fall $d_n = L, i_n > 1$}
\label{fig:wordNaviLig1}
\end{figure}

Im Falle von $d_n = R$ haben wir drei Unterfälle zu betrachten. Ist $X_n = S$, so sind wir am Textende angelangt. Wir können folglich nicht weiter nach rechts gehen und lassen den Stack unverändert. Sei also $X_n \not= S$. Wir können im Ableitungsbaum nicht weiter nach rechts ableiten, da  $R_{i_n}(X_n) \in \Sigma$ ist. Wir verwerfen den Top-Stack. Aufgrund von (ii) muss $t_{n-1}$ eine Linkskette sein. Wir müssen zwei Fälle unterscheiden.

\

Fall $i_{n-1} = 1$: Der Knoten $X_{n-1}$ ist der LCA. Wir haben zwei Unterfälle zu betrachten.

\begin{itemize}
\item	Ist $X_{n-1} = S$, so ersetzen wir $t_{n-1}$ durch $\langle S, 1, R\rangle$. Wir gelangen zum Knoten $X_n' = R_1(S)$. Dieser Fall ist ähnlich dem Fall $X_n = S, i_n = 1, d_n = L$.

\item	Ist $X_{n-1} \not= S$, so gibt es eine Rechtskette $t_{n-2}$. Diese verlängern wir um einen Schritt und ersetzen sie im Stack durch $\langle X_{n-2}, k, R\rangle$ mit $k = i_{n-2}+1$. Wir gelangen zum Knoten $X_n' = R_k(X_{n-2})$. Hierzu ist der Fall $X_ n \not= S, i_n = 1, d_n = L$ ähnlich.
\end{itemize}

In beiden Unterfällen haben wir das nächste Textsymbol gefunden, falls $X_n' \in \Sigma$ ist. Andernfalls finden wir das nächste Textsymbol wieder im am weitesten links stehenden Symbol des Teilableitungsbaum $\tree_G(X_n')$ und fügen $\langle X_n', H(X_n'), L\rangle$ zum Stack hinzu.

\

Fall $i_{n-1} > 1$: Wir kürzen die Linkskette um einen Schritt. Der LCA ist der Knoten $X_v = L_k(X_{n-1})$ mit $k = i_{n-1} - 1$. Wir ersetzen $t_{n-1}$ durch $\langle X_{n-1}, k, L\rangle$. Vom LCA aus gehen wir einen Schritt nach rechts, d.\,h. wir fügen $\langle X_v, 1, R\rangle$ zum Stack hinzu. Wie in den vorherigen Fällen ist entweder $X_n' = R_1(X_v) \in \Sigma$, und damit das nächste Textsymbol, oder aber $X_n'$ spannt den Teilableitungsbaum $\tree_G(X_n')$ auf, womit das nächste Textsymbol gleich $L_{H(X_n')}(X_n')$ ist. Dann müssen wir noch $\langle X_n', H(X_n'), L\rangle$ zum Stack hinzufügen. Bildlich ist der Fall in Abbildung \ref{fig:wordNaviRnSig1} dargestellt.

\begin{figure}[h]
\begin{center}
\begin{picture}(60,42)(0,-40)
\gasset{Nframe=n,AHnb=0,Nw=6,Nh=6}
\node(nX1)(46,0){\rput{333}(0,0){...}}
\node[Nw=10](nXn-1)(60,-7){$X_{n-1}$}
\node(nXn-1r)(74,-14){\rput{333}(0,0){...}}
\node(nXv)(30,-22){$X_v$}
\node(nXn)(10,-32){$X_ n$}
\node(nXnl)(-2,-38){\rput{30}(0,0){...}}
\node[NLdist=-2.5,Nw=0](nXna)(22,-38){$a$}
\node(nXns)(50,-32){$X_n'$}
\node[NLdist=-2.5,Nw=0](ndl)(42,-42){$a$}
\node[Nw=0.1,Nh=0.1](ndr)(58,-42){}

\drawedge(nX1,nXn-1){}
\drawedge(nXn-1,nXn-1r){}
\drawedge[ELside=r,ELpos=70](nXn-1,nXv){\small$i_{n-1}-1$}
\drawedge[ELside=r](nXv,nXn){\small 1}
\drawedge(nXv,nXns){\small 1}
\drawedge(nXn,nXnl){}
\drawedge[ELpos=65](nXn,nXna){\small$i_n$}
\drawedge[sxo=2.7](nXns,ndl){}
\drawedge[sxo=-4.1](nXns,ndr){}
\drawedge(ndl,ndr){}
\end{picture}
\end{center}
\caption{Fall $d_n = R, X_n \not= S, i_{n-1} > 1$}
\label{fig:wordNaviRnSig1}
\end{figure}

\subsection{Linksschritt}
Wir können im Text auch rückwärts gehen. Auch hier müssen wir anhand des aktuellen Stacks entscheiden. Wir werden hier jedoch nur die Ersetzungen im Stack angeben, da die Begründungen hierfür analog zu denen für den Rechtsschritt sind.

\

Für den Fall $d_n = R$ haben wir drei Unterfälle zu betrachten.

\vspace{8pt}Fall $i_n > 1$: Wir ersetzen $t_n$ durch $\langle X_n, k, R\rangle$ und fügen $\langle X_v, 1, L\rangle$ zum Stack hinzu wobei $k = i_n-1$ und $X_v = L_k(X_n)$ ist. Ist nun auch $X_n' = L_1(X_v) \in N$, so fügen wir auch $\langle X_n', W(X_n'), R\rangle$ zum Stack hinzu.

\vspace{8pt}Fall $i_n = 1, X_n = S$: Wir ersetzen $t_n$ durch $\langle S, 1, L\rangle$. Ist zudem $L_1(S) \in N$ , so legen wir auch $\langle L_1(S), W(L_1(S)), R\rangle$ auf den Stack.

\vspace{8pt}Fall $i_n = 1, X_n \not= S$: Wir entfernen $t_n$. Durch (ii) muss $t_{n-1}$ eine Linkskette sein, wir ersetzen somit $t_{n-1}$ durch $\langle X_{n-1}, k, L\rangle$ mit $k = i_{n-1}+1$. Ist $X_n' = L_k(X_{n-1}) \in N$, so müssen wir wie gehabt auch $\langle X_n', W(X_n'), R\rangle$ dem Stack hinzufügen.

\

Im Fall $d_n = L$ müssen wir drei Unterfälle betrachten. Ist $X_n = S$, so sind wir am Textanfang angelangt und können nicht weiter nach links. Der Stack bleibt unverändert. Sei also $X_n \not= S$. Wir löschen $t_n$ vom Stack. Der Tripel $t_{n-1}$ muss wegen (ii) eine Rechtskette sein. Wir haben zwei Fälle zu unterscheiden.

\vspace{8pt}Fall $i_{n-1} > 1$: Wir ersetzen $t_{n-1}$ durch $\langle X_{n-1}, k, R\rangle$ mit $k = i_{n-1}-1$ und fügen $\langle X_v, 1, L\rangle$ zum Stack hinzu wobei $X_v = R_k(X_{n-1})$ ist. Ist zudem $L_1(X_v) \in N$, so legen wir auch $\langle L_1(X_v), W(L_1(X_v)), R\rangle$ auf den Stack.

\vspace{8pt}Fall $i_{n-1} = 1$: Wir entfernen $t_{n-1}$ vom Stack und müssen wieder zwei Unterfälle betrachten.
Ist $X_{n-1} = S$, dann fügen wir $\langle S, 1, L\rangle$ zum Stack hinzu. Ist zudem $L_1(S) \in N$, so packen wir auch $\langle L_1(S), W(L_1(S)), R\rangle$ auf den Stack. 
Ist $X_{n-1} \not= S$, dann gibt es eine Linkskette $t_{n-2}$. Wir ersetzen nun $t_{n-2}$ durch $\langle X_{n-2}, k, L\rangle$ mit $k = i_{n-2}+1$ und fügen, falls $X_n' = L_k(X_{n-2}) \in N$ ist, auch $\langle X_n', W(X_n'), R\rangle$ zum Stack hinzu.

\begin{satz}
Es gibt einen Algorithmus mit dem wir in einem durch eine Straight-Line-Grammatik $G = (N, P, S)$ komprimierten Text in Platz $O(|P|^2)$ und konstanter Zeit pro Symbol navigieren können.
\end{satz}

\begin{bew}
Wir berechnen zuerst aus der Straight-Line-Grammatik $G$ die Abbildungen $L$ und $R$. Diese benötigen bekanntlich Platz $O(|P|^2)$. Den Stack $T$ initialisieren wir auf das erste Symbol im Text, also mit dem Wert $[\langle S,H(S),L\rangle]$. Anschließend verarbeiten wir die Richtungsanweisungen und aktualisieren den Stack entsprechend der in Kapitel 2.4 vorgestellten Weise. Wir nehmen dort nur konstant viele Ersetzungen durch, somit ist der Zeitbedarf pro Navigationsschritt -- und somit pro Symbol -- gleich $O(1)$.
\end{bew}


%==================================================================================%


\chapter{Baumgrammatiken}
Unser Ziel ist die Verallgemeinerung der Resultate aus Kapitel 2 auf Bäume. Dazu wollen wir zunächst erst einmal definieren was Bäume und insbesondere Baumgrammatiken sind. Wir werden im Rahmen dieser Arbeit nur Bäume über einem Rangalphabet betrachten.

\section{Grundlegende Definitionen} 
\begin{defin}
Sei $\F$ eine endliche Menge von Funktionssymbolen und $\rank : \F \ra \N$ eine Abbildung, die jedem $f \in \F$ einen Rang $\rank(f)$ zuweist. Ein \emph{Rangalphabet} ist ein Paar $(\F, \rank)$. Weiterhin definieren wir die Mengen $\F_i := \{f \in \F \mid \rank(f) = i\}$. Wir nennen $f \in \F_i$ auch $i$-stelliges Symbol und Elemente aus $\F_0$ insbesondere auch Konstanten. Ist die Abbildung $\rank$ bekannt, so bezeichnen wir der Einfachheit halber auch nur $\F$ als Rangalphabet.
\end{defin}

\begin{defin}
\label{defin:ftree}
Sei $(\F, \rank)$ ein Rangalphabet. Ein $\F$-\emph{beschrifteter, geordneter Baum} $t$ ist ein Paar $(\dom(t), \lambda_t)$ bestehend aus einer endlichen, nicht-leeren Menge $\dom(t) \subseteq \N^*$  und einer Abbildung $\lambda_t : \dom(t) \ra \F$. Zusätzlich gilt:
\begin{enumerate}
\item Ist $w = v.v' \in \dom(t)$, so ist auch $v \in \dom(t)$ mit $v, v' \in \N^*$.
\item Ist $v \in \dom(t)$ und $\lambda_t(v) \in \F_n$, dann ist $v.i \in \dom(t)$ genau dann wenn $1 \leq i \leq n$.
\end{enumerate}
Wir nennen die Elemente von $\dom(t)$ Knoten und die Wurzel von $t$ bezeichnen wir mit $\veps \in \dom(t)$. Die Kantenrelation des Baumes $t$ ergibt sich implizit als Relation $E(t) = \{(v, v.i) \mid v \in \dom(t), i \in \N\}$. Den Knoten $v.i$ nennen wir das $i$-te Kind oder auch den $i$-ten Sohn von $v$. Die Größe von $t$ ist definiert als $|t| = |\dom(t)|$.
\end{defin}

 Wenn wir in der weiteren Arbeit von Bäumen sprechen werden, dann sind damit stets $\F$-beschriftete, geordnete Bäume gemeint.

\begin{bsp}
\label{bsp:tree}
Sei $\F = \{a, f, g, h\}$ wobei $a$ eine Konstante, $h$ ein einstelliges, $f$ ein zweistelliges und $g$ ein dreistelliges Symbol ist. Sei nun $t = (\dom(t), \lambda_t)$ ein Baum mit $\dom(t) = \{\veps, 1, 1.1, 1.2, 2, 3, 3.1, 3.1.1, 3.2, 3.2.1, 3.2.2\}$ und 
\[\lambda_t(v) =
\begin{cases}
	g 	&	\textrm{falls } v = \veps										\\
	f	&	\textrm{falls } v \in \{1, 3, 3.1, 3.2\}						\\
	h 	&	\textrm{falls } v = 3.1												\\
	a	&	\textrm{sonst}	\\
\end{cases}	\]
\end{bsp}

Die Lesbarkeit solcher Bäume ist jedoch nicht sehr hoch. Es gibt verschiedene Ausdrucksweisen um einen konkreten Baum leichter verständlich zu machen. Zum einen können wir einen Baum $t$ als einen Graphen darstellen. Als Knotenmenge verwenden wir $\dom(t)$ und als Kantenrelation nutzen wir die in Definition \ref{defin:ftree} definierte Relation $E(t)$. Zum anderen können wir jeden Baum mit einem Term identifizieren. Ist $\lambda_t(\veps) = f \in \F_n$, so identifizieren wir ihn mit dem \emph{Term} $f(t_1, \ldots, t_n)$ wobei $t_i$ der Term ist, den wir mit dem Teilbaum $i$ identifizieren. Für Konstanten $a$ verwenden wir statt $a()$ den Term $a$. Wir nennen $t$ auch \emph{Grundterm} (\emph{über} $\F$). Die Menge aller Grundterme (über $\F$) bezeichnen wir mit $\T(\F)$. Diese Ausdrucksweise erlaubt es uns leichter mit Bäumen zu arbeiten. Wir werden daher im Rest der Arbeit Bäume und ihre entsprechenden Term synonym verwenden.

\begin{bsp}
Sei $t$ der Baum aus Beispiel \ref{bsp:tree}. Wir können den Baum mit dem Term $g(f(a, a), a, f(h(a), f(a, a)))$ identifizieren. Eine Darstellung als Graph zeigt die Abbildung \ref{fig:tree}. 
\begin{figure}[h]
\begin{center}
\begin{picture}(38,36)(0,-34)
\gasset{Nframe=n,AHnb=0,Nw=5,Nh=5}
\node(nveps)(16,0){$g$}
\node(n1)(4,-12){$f$}
\node(n2)(16,-12){$a$}
\node(n3)(28,-12){$f$}
\node(n11)(0,-24){$a$}
\node(n12)(8,-24){$a$}
\node(n31)(22,-24){$h$}
\node(n32)(34,-24){$f$}
\node(n311)(22,-36){$a$}
\node(n321)(30,-36){$a$}
\node(n322)(38,-36){$a$}

\drawedge(nveps,n1){}
\drawedge(nveps,n2){}
\drawedge(nveps,n3){}
\drawedge(n1,n11){}
\drawedge(n1,n12){}
\drawedge(n3,n31){}
\drawedge(n3,n32){}
\drawedge(n31,n311){}
\drawedge(n32,n321){}
\drawedge(n32,n322){}
\end{picture}
\end{center}
\caption{Darstellung des Baumes $t$ als Graph}
\label{fig:tree}
\end{figure}
\end{bsp}

Sei $\Y = \{y_1, y_2, \ldots\}$ eine abzählbare, unendliche Menge von \emph{Parametern} und $\omega \not\in \Y$ ein weiterer Parameter. Die Menge aller Grundterme mit Parametern aus $Y \subseteq \Y$ nennen wir $\T(\F, Y)$. Parameter betrachten wir formal als neue Konstanten und setzen deshalb $\T(\F, Y) := \T(\F \dcup Y)$. Dabei bezeichnet $\dcup$ die disjunkte Vereinigung zweier Mengen. Ein Baum $t \in \T(\F, Y)$ ist \emph{linear}, wenn jeder Parameter $y \in Y$ höchstens einmal in $t$ vorkommt. Ein \emph{Kontext} ist ein Baum $C \in \T(\F, Y \cup \{\omega\})$ in dem der Parameter $\omega$ genau einmal auftaucht. Damit können wir nun die Substitution definieren. 

\begin{defin}[Substitution]
Sei $t = f(s_1, \ldots, s_m)$ ein Baum aus $\T(\F, \{y_1, \ldots, y_n\})$ und seien $t_1, \ldots, t_n$ Bäume aus $\T(\F, Y)$ für $f \in \F_m$ und $m,n \in \N$.  Wir erhalten den Baum $t[y_1/t_1, \ldots, y_n/t_n]$ induktiv durch
\[
	t[y_1/t_1, \ldots, y_n/t_n] := \begin{cases}
		t_i 	&	\textrm{falls } t = y_i 	\\
		f(s_1[y_1/t_1, \ldots, y_n/t_n], \ldots, s_m[y_1/t_1, \ldots, y_n/t_n])	&	\textrm{sonst}
	\end{cases}
\]
Ist $C$ ein Kontext, so schreiben wir der Einfachheit halber statt $C[\omega/t]$ nur $C[t]$.
\end{defin}

\begin{bsp}
Sei $\F$ das Rangalphabet aus Beispiel \ref{bsp:tree} und $Y=\{y_1, y_2\}$. Sei außerdem $t = f(y_1, f(y_2, a))$ ein Baum. Dann ist 
\[	\begin{array}{lcl}
	t[y_1/h(\omega), y_2/f(a,a)]	&	=	&	f(y_1[y_1/h(\omega), y_2/f(a, a)], f(y_2, a)[y_1/h(\omega), y_2/f(a, a)])	\\
												&	=	&	f(h(\omega), f(y_2[y_1/h(\omega), y_2/f(a, a)], a[y_1/h(\omega), y_2/f(a,a)]))	\\
												&	=	&	f(h(\omega), f(f(a, a), a))
	\end{array}
	\vspace{2pt} \]
Das Ergebnis ist zudem ein Kontext.
\end{bsp}

Seien nun $\mathcal{N}_i$ abzählbare, unendliche Mengen von Symbolen von Rang $i$ mit 	$\mathcal{N}_i \cap \F_i = \emptyset$. Es ist klar, dass jede endliche Teilmenge $N \subseteq \bigcup_{i \geq 0} \mathcal{N}_i$ ein Rangalphabet darstellt. Damit haben wir alle Voraussetzungen erfüllt und können jetzt Baumgrammatiken definieren.

\begin{defin}
Sei $\F$ ein Rangalphabet. Eine \emph{kontextfreie Baumgrammatik} (über $\F$) ist ein Tripel $G = (N, P, S)$ wobei 
\begin{itemize}
\item $N \subseteq \bigcup_{i \geq 0} \N_i$ eine endliche Menge ist,
\item $P \subseteq N \times \T(\F \cup N, Y)$ eine endliche Menge von Regeln der Form $A \ra t$ ist mit $t \in \T(\F \cup N, \{y_1, \ldots, y_{\rank(A)}\})$ und
\item $S \in N \cap \mathcal{N}_0$ das Startsymbol ist.
\end{itemize}
\end{defin}

Die Elemente von $\F$ nennen wir wieder Terminalsymbole, die Elemente von $N$ nennen wir ebenfalls wie zuvor Nichtterminalsymbole. Ohne Einschränkung können wir voraussetzen, dass alle Nichtterminale $B \in N \minus \{S\}$ sowie alle Terminale aus $\F$ in mindestens einer Regel $A \ra t_A$ auf der rechten Seite $t_A$ vorkommen. Auch schließen wir in den Regeln Umbenennungen aus, also Regeln der Form $A \ra C$ für $A, C \in N$. Um hervorzuheben, dass $\rank(A) = n$ ist, schreiben wir die Regel $A \ra t$ auch in der Form $A(y_1, \ldots, y_n) \ra t$. Dies erleichtert uns das Verständnis der Regeln.

\

Mit kontextfreien Wortgrammatiken konnten wir Sprachen über endlichen Wörtern definieren. Analog wollen wir mit kontextfreie Baumgrammatiken Sprachen über endlichen Bäumen definieren. Dazu benötigen wir den Begriff der Ableitungen.

\begin{defin}[Ableitungsrelation]
Sei $G = (N, P, S)$ eine kontextfreie Baumgrammatik und seien $s, s' \in \T(\F \cup N, Y)$. Wir können $s$ nach $s'$ ableiten, kurz $s \Ra_G s'$, wenn es eine Regel $(A \ra t) \in P$ mit $\rank(A) = n$, Bäume $t_1, \ldots, t_n \in \T(\F \cup N, \Y)$ und einen Kontext $C \in \T(\F \cup N, Y \cup \{\omega\})$ gibt, so dass $s = C[A(t_1, \ldots, t_n)]$ und $s' = C[t[y_1/t_1,  \ldots, y_n/t_n]]$ gilt.
Wir nennen $\Ra_G$ die \emph{Ableitungsrelation} von $G$ und mit $\Ra_G^*$ bezeichnen wir den reflexiv transitiven Abschluss von $\Ra_G$. Die \emph{Baumsprache} von $G$ ist die Menge $L(G) := \{t \in \T(\F) \mid S \Ra_G^* t\}$. Zwei kontextfreie Baumgrammatiken $G$ und $G'$ sind \emph{äquivalent}, falls $L(G) = L(G')$ ist.
\end{defin}

Um das Ganze besser zu verstehen, wollen wir uns zunächst Beispiele ansehen.

\begin{bsp}\label{bsp:treeGrammar}
Sei $G = (N, P, S_0)$ eine kontextfreie Baumgrammatik mit $N = \{S_0, S_1\}$. Die Regelmenge $P$ enthält die Regeln (1) $S_0 \ra S_1(a, b)$, (2) $S_1(y_1, y_2) \ra f(y_1, y_2)$ und (3) $S_1(y_1, y_2) \ra S_1(S_1(y_1,y_1), S_1(y_2,y_2))$. 

\

Es ist klar, dass wir das Startsymbol $S_0$ mit der Regel (1) und dem Kontext $C=\omega$ zu $S_1(a, b)$ ableiten können. Der Term $S_1(a, b)$ wiederum kann mit der Regel (3), den Bäumen $t_1 = a, t_2 = b$ und dem Kontext $C=\omega$ zu $S_1(S_1(a,a),S_1(b,b))$ abgeleitet werden, denn es gilt
\[ \begin{array}{l}
	C[S_1(t_1,t_2)] = S_1(a, b) \\
	C[S_1(S_1(x, x), S_1(y, y))[x/t_1, y/t_2]] = S_1(S_1(a, a), S_1(b, b))
	\end{array} \]
Wir können $S_1(S_1(a, a), S_1(b, b))$ mit der Regel (2), den Bäumen $t_1 = t_2 = a$ und dem Kontext $C = S_1(\omega, S_1(b, b))$ zu $S_1(f(a, a), S_1(b, b))$ ableiten. Wenden wir Regel (3) noch zweimal an so erhalten wir $f(f(a, a), f(b, b))$. Wir sehen nun, dass $L(G)$ die Menge aller vollständigen binären Bäume über $\F$ ist deren Blätter von links nach rechts gelesen das Wort $a^{2^n}b^{2^n}$ für $n \in \N$ ergeben.
\end{bsp}

Anhand des Beispiels \ref{bsp:treeGrammar} haben wir außerdem gesehen, dass wir mit kontextfreien Baum\-grammatiken unendlich viele Bäume erzeugen können. Wir benötigen jedoch Baumgrammatiken die genau einen Baum erzeugen. Unser Ziel ist es, die Ergebnisse aus Kapitel 2 auf Bäume über einem Rangalphabet zu verallgemeinern. Deshalb werden wir die Definition der Straight-Line-Wort\-gram\-ma\-ti\-ken auf Bäume verallgemeinern. Wir werden vorher aber noch zeigen, dass Baumgrammatiken eine Verallgemeinerung von Wortgrammatiken darstellen.

\begin{lemma}
Sei $G= (N, P, S)$ eine kontextfreie Wortgrammatik über einem end\-lichen Alphabet $\Sigma$. Dann gibt es ein Rangalphabet $\F$ und eine kontextfreie Baumgrammatik $G'$ über $\F$, so dass gilt: Ist $w \in L(G)$, dann gibt es einen Baum $t_w \in \T(\F)$ mit $t_w \in L(G')$ und umgedreht.
\end{lemma}

\begin{bew}
Mit Satz \ref{satz:wordCNF} können wir voraussetzen, dass $G$ in Chomsky-Normal\-form ist. Als Symbole des Rangalphabets verwenden wir $\F := \Sigma \cup \{\bot\}$. Dabei ist $\rank(a) = 1$ für alle $a \in \Sigma$ und $\bot \not\in \Sigma$ ist eine neue Konstante. Sei nun $w = a_1 \ldots a_n \in \Sigma^*$ ein beliebiges Wort. Wir konstruieren uns den Baum $t_w := a_1(\ldots(a_n(\bot))\ldots)$.

\

Wir müssen noch die Baumgrammatik angeben. Sei dazu $N' := N \dcup \{S_0, S_{\bot}\}$ wobei $S_0$ und $S_{\bot}$ zwei neue Nichtterminale  von Rang 0 sind. Für alle $A \in N$ gilt $\rank(A) = 1$. Die Regelmenge $P'$ enthält die Regeln $S_0 \ra S(S_{\bot})$ und $S_{\bot} \ra \bot$. Außerdem fügen wir für jede Regel $(A \ra BC) \in P$ eine Regel $A(x) \ra B(C(x))$ und für jede Regel $(A \ra a) \in P$ eine Regel $A(x) \ra a(x)$ hinzu.

\

Wir sehen sofort, dass $G' = (N', P', S_0)$ eine kontextfreie Baumgrammatik ist. Sei nun $w \in L(G)$. Dann gibt es eine bei $S_0$ startende Folge von Ableitungen
\[
S=w_0 \xRightarrow{r_1\;}_G
w_1 \xRightarrow{r_2\;}_G
w_2 \Ra_G \ldots \Ra_G
w_{n-1} \xRightarrow{r_n\;}_G
w_n = w
\]
Dabei bedeutet $\xRightarrow{r}_G$, dass mittels der Regel $r \in P$ in der Grammatik $G$ abgeleitet wurde. Damit $t_w$ von $G'$ erzeugt werden kann, müssen wir eine bei $S_0$ startende und bei $t_w$ endende Ableitungsfolge konstruieren. Betrachte die Folge 
\[
S_0 \xRightarrow{S_0 \ra S(S_{\bot})\;}_{G'}
S(S_{\bot}) \xRightarrow{S_{\bot} \ra \bot\;}_{G'}
S(\bot) = t_w^0 \xRightarrow{r_1'\;}_{G'}
t_w^1 \Ra_{G'} \ldots \Ra_{G'}
t_w^{n-1} \xRightarrow{r_n'\;}_{G'}
t_w^n = t_w
\]
wobei $r_i'$ die Regel ist die wir in der Konstruktion von $P'$ aus der Regel $r_i$ erhalten. Wir zeigen nun induktiv: Ist $w_i = A_1 \ldots A_m$, dann ist $t_w^i = A_1(\ldots(A_m(\bot))\ldots)$ mit $0 \leq i \leq n$ und $m \in \N$.

\begin{description}
\item[Induktionsanfang] Die Aussage gilt für $i = 0$, denn $w_0 = S$ und $t_w^0 = S(\bot)$.

\item[Induktionsvoraussetzung] Gelte die Aussage für $i-1$.

\item[Induktionsschluss] Sei also $w_{i-1} = A_1 \ldots A_{j-1}A_jA_{j+1} \ldots A_n$ für $1 \leq j \leq m$. In $G$ haben wir die Regel $r_i = (A_j \ra B_jC_j)$ angewendet und $w_i = A_1 \ldots A_{j-1} B_jC_j A_{j+1} \ldots A_m$  erhalten. Nach Induktionsvoraussetzung gilt
\[ t_w^{i-1} = A_1(\ldots(A_{j-1}(A_j(A_{j+1}(\ldots(A_m(\bot))\ldots))))\ldots)\]
Aus der Konstruktion von $P'$ erhalten wir die Regel $r_i' = (A_j(x) \ra B_j(C_j(x)))$. Mit Hilfe dieser Regel, dem Kontext $C = A_1(\ldots(A_{j-1}(\omega))\ldots)$ und dem Baum $t_1 = A_{j+1}(\ldots A_m(\bot))$ können wir $t_w^{i-1}$ zum Baum 
\[ t_w^i = A_1(\ldots(A_{j-1}(B_j(C_j(A_{j+1}(\ldots(A_m(\bot))\ldots)))))\ldots)\]
ableiten. Der zweite Fall $r_i = (A_j \ra a_j)$ geht auf analoge Art und Weise. Damit gilt die Induktionshypothese auch für $i$.
\end{description}

Da $w_n = w$ ist, folgt damit $t_w^n = t_w$. Die Folge in $G'$ erzeugt also $t_w$. Die umgedrehte Richtung des Beweises verläuft analog.\hfill$\Box$
\end{bew}

\section{Straight-Line-Baumgrammatiken}
\begin{defin}
Eine \emph{Straight-Line-Baumgrammatik} ist eine kontextfreie Baumgrammatik $G = (N, P, S)$ für die zusätzlich gilt:
\begin{itemize}
  \item Für jedes $A \in N$ gibt es genau eine Regel $(A \ra t_A) \in P$.
  \item Die Relation $R = \{(A,B) \in N \times N \mid B$ taucht in $t_A$ auf$\}$ ist azyklisch.
\end{itemize}
\end{defin}

Der Determinismus und die Azyklizität der Regeln stellen sicher, dass $L(G)$ genau ein Element enthält. Diesen Baum bezeichnen wir wieder, ähnlich wie im Fall der Wortgrammatiken, mit $\val(G)$. Bevor wir uns der Navigation im Baum zuwenden, wollen wir uns noch zwei Beispiele für Straight-Line-Baumgrammatiken anschauen.

\begin{bsp}\label{bsp:treeSlg}
Sei $t = g(f(a, a), a, f(h(a), f(a, a)))$ der Baum aus Beispiel \ref{bsp:tree}. Er kann durch eine Straight-Line-Baumgrammatik $G$ mit folgenden Regeln erzeugt werden:
\[ \begin{array}{lp{15mm}l}
	\vspace{4pt}A_0 \ra A_1(A_2)						&	&	A_3(x) \ra f(x, x)				\\
	\vspace{4pt}A_1(x) \ra g(A_3(x), x, A_4(x)) 	&	&	A_4(x) \ra f(h(x), A_3(x))	\\
	\vspace{4pt}A_2 \ra a									&	&											\\
	\end{array}	\]
Dann ist $\val(G) = t$.
\end{bsp}

\begin{bsp}\label{bsp:Hn}
Betrachten wir noch einmal das Beispiel \ref{bsp:slcfGrammar}.2, genauer die Wortgrammatik $G_n = (N_n, P_n, A_0)$. Abbildung \ref{fig:slpDerivTree} zeigte den Ableitungsbaum von $G_n$. Diesen können wir auch als $\F^n$-beschrifteten, geordneten Baum über einem geeigneten Rangalphabet $\F^n$ auffassen. Dazu wählen wir $\F^n = \Sigma \cup N_n$ mit $\rank(a) = 0$ und $\rank(A) = 2$ für alle $a \in \Sigma, A \in N_n$.

\

Wir definieren uns die Straight-Line-Baumgrammatik $H_n = (N_n', P_n', B_0)$. Die Menge der Nichtterminale definieren wir als $N_n' = \{B_i, B_i^1 \mid 0 \leq i \leq n\} \cup \{B_n^2, B_n^3\}$. Dabei sind $B_n^2, B_n^3$ und alle $B_i$ neue Nichtterminale von Rang 0. Alle $B_i^1$ sind neue Nichtterminale von Rang 1. An Regeln enthält $P_n'$ nun
\[	\begin{array}{lp{3cm}r}
	\vspace{4pt}B_i \ra B_i^1(B_{i+1})					& 	&	(\textrm{für alle } 0 \leq i < n) \\
	\vspace{4pt}B_i^1(y_1) \ra A_i(y_1, B_{i+1})
	\end{array} \]
sowie $B_n \ra B_n^1(B_n^2)$ und $B_n^1(y_1) \ra A_n(y_1, B_n^3)$. Zusätzlich sind noch $B_n^2 \ra a$ und $B_n^3 \ra c$ Regeln von $P_n'$.

\

Es ist leicht zu zeigen, dass $B_0 \Ra_H^* A_0(A_1(\ldots(A_n(a, c), \ldots)\ldots), A_1(\ldots))$ gilt. Dies ist die Termdarstellung des Ableitungsbaumes von $G_n$. Somit ist $\val(H_n) = \tree_{G_n}(\val(G_n))$.
\end{bsp}


%==================================================================================%

\chapter{Traversierung in grammatikkomprimierten Bäumen}
Straight-Line-Wortgrammatiken haben jeweils genau ein Wort über einem Alphabet $\Sigma$ erzeugt. Mit Hilfe des Navigationsalgorithmus konnten wir uns in diesem nach links und rechts bewegen ohne es komplett entschlüsselt zu haben. Straight-Line-Baum\-gramma\-tiken erzeugen ebenfalls jeweils genau einen Baum. Wir wollen uns auch in diesem zwischen den Knoten bewegen können ohne den Baum komplett zu erzeugen. Dazu benötigen wir Operationen mit denen wir sowohl zu den einzelnen Kindern eines Knotens als auch zum Vaterknoten navi\-gieren können. Wir werden uns jedoch zuerst einmal auf eine Unterklasse von Straight-Line-Grammatiken einschränken.

\section{Voraussetzungen}
Im Wortfall haben wir sowohl für die Traversierung, als auch für die Navigation, Straight-Line-Grammatiken verwendet, welche mittels eines Recursive-Pairing-Algorithmus erzeugt wurden. Sie waren an die Chomsky-Normalform angelehnt. Dadurch gab es nur eine Art von Regeln, und zwar $A \ra BC$ für Nichtterminale $A, B$ und $C$. Dies erleichterte uns den Aufbau des Algorithmus sowie die Beweisführung. In Straight-Line-Baumgrammatiken $G = (N, P, S)$ über $\F$ haben wir Regeln der Form $A \ra t$ mit $t \in \T(\F \cup N, Y)$. Der Baum $t$ kann jedoch theoretisch beliebig groß sein. Deshalb werden wir auch hier die Regeln normalisieren.

\begin{defin}
Sei $G = (N, P, S)$ eine Straight-Line-Baumgrammatik.
\begin{itemize}
  \item $G$ ist \emph{linear}, wenn in jeder Regel $(A \ra t) \in P$ der Baum $t$ linear ist.
  \item $G$ ist \emph{erhaltend} (non-deleting), wenn für jede Regel $(A \ra t)$ jeder der Parameter $y_1, \ldots, y_{\rank(A)}$ in $t$ vorkommt.
  \item $G$ ist \emph{nicht-löschend} (non-erasing), falls $t \not\in \Y$ für jede Regel $(A \ra t) \in P$.
  \item $G$ ist \emph{produktiv}, falls sie erhaltend und nicht-löschend ist.
  \item $G$ ist $k$-\emph{beschränkt} für $k \in \N$, falls $\rank(A) \leq k$ für alle $A \in N$.
  \item $G$ ist \emph{monadisch}, falls sie 1-beschränkt ist.
\end{itemize}
\end{defin}

\begin{lemma}
Sei $G = (N, P, S)$ eine lineare Straight-Line-Baumgrammatik. Dann gibt es eine äquivalente lineare, erhaltende Straight-Line-Baumgrammatik. Sie kann in polynomieller Zeit aus $G$ konstruiert werden und ist gleich groß.
\end{lemma}

\begin{bew}
Für jede Regel der Form $A(y_1, \ldots, y_n) \ra t$ in der die Parameter $y_{i_1}, \ldots, y_{i_m}$ nicht vorkommen, führen wir folgende Schritte aus:
\begin{itemize}
\item Wir reduzieren den Rang von $A$ auf $n - m$ und benennen die verbliebenen Variablen passend um.
\item In jeder anderen Regel $B \ra t_B$ löschen wir in jedem Vorkommen von $A(t_1, \ldots, t_n$) die Teilbäume $t_{i_1}, \ldots, t_{i_m}$.
\end{itemize}

Wir müssen jede Regel einmal prüfen und im Falle von Ersetzungen einmal mit jeder anderen Regel vergleichen. Die Anzahl der Regeln bleibt dabei gleich. Es ist offensichtlich, dass die so konstruierte Straight-Line-Baumgrammatik linear, erhaltend und äquivalent zu $G$ ist.\hfill$\Box$
\end{bew}

\begin{lemma}
Sei $G = (N, P, S)$ eine lineare, erhaltende Straight-Line-Baum\-gramma\-tik. Dann gibt es eine äquivalente lineare, produktive \mbox{Straight-Line-Baumgrammatik. Sie} kann in polynomieller Zeit aus $G$ erzeugt werden und ist höchstens so groß wie $G$.
\end{lemma}

\begin{bew}
Da $G$ erhaltend ist, können nur Regeln der Form $A(y_1) \ra y_1$ die Bedingung verletzen für $A \in N$. Wir wenden folgende Schritte an:
\begin{itemize}
\item Wir wenden in allen anderen Regeln $B \ra t_B$ die Regel $A(y_1) \ra y_1$ auf $t_B$ an.
\item Wir löschen die Regel aus der Regelmenge.
\end{itemize}

Zur Berechnung müssen wir alle Regeln einmal durchgehen und im Falle von Ersetzungen mit jeder anderen Regel vergleichen. Da wir nur Regeln umschreiben und löschen, ist die Anzahl höchstens so groß wie  in $G$. Die neu konstruierte Straight-Line-Baumgrammatik ist linear, produktiv und äquivalent zu $G$.\hfill$\Box$
\end{bew}

Damit können wir für den Rest der Arbeit davon ausgehen, dass alle linearen Straight-Line-Baumgrammatiken auch produktiv sind. Sei $\F := \F_0 \dcup \F_2$ wobei $\F_0$ und $\F_2$ zwei nicht-leere, disjunkte Mengen sind mit $\rank(f) = i$ für $f \in \F_i$.Wir schränken uns zu Beginn auf  lineare, monadische Straight-Line-Baumgrammatiken über dem Rangalphabet $(\F, \rank)$ ein. Das ermöglicht uns die Regeln in zwei Typen einzuteilen.

\

Seien dazu $A, B$ und $C$ Nichtterminale und $a, f$ Terminalsymbole. Typ-1-Regeln haben die Form 
\begin{enumerate}
  \item $A \ra B(C)$
  \item $A(x) \ra B(C(x))$
\end{enumerate}
Typ-2-Regeln haben die Form
\begin{enumerate}
  \item $A \ra a$
  \item $A(x) \ra f(B, x)$ oder $A(x) \ra f(x, B)$
\end{enumerate}
Wir nennen $A$ dann auch entsprechend Typ-1- beziehungsweise Typ-2-Nichtterminal. Im weiteren Verlauf der Arbeit werden wir nur noch solche eingeschränkten Straight-Line-Baumgrammatiken betrachten. Wir können mit diesem Regelsatz alle Bäume über $\F$ erzeugen. Dies zeigen wir noch einmal kurz im folgenden Lemma.

\begin{lemma}\label{lemma:createsAll}
Sei $t \in \T(\F)$ ein Baum. Dann gibt es eine Straight-Line-Baumgrammatik $G$ die $t$ erzeugt, also für die $\val(G) = t$ ist.
\end{lemma}

\begin{bew}
Per Induktion über den Aufbau der Bäume zeigen wir das Lemma.

\begin{description}
\item[Induktionsanfang]	Sei $t = a$ für ein beliebiges $a \in \F_0$. Dann ist $G = (N, P, S_0)$ mit der Nichtterminalmenge $N = \{S_0\}$, der Regelmenge $P = \{S_0 \ra a\}$ eine Straight-Line-Baumgrammatik mit $\val(G) = a$.

\item[Induktionsschritt]	Sei $t = f(t_1, t_2)$ wobei $f \in \F_2$ ein beliebiges Terminalsymbol ist und $t_1, t_2$ Bäume sind für die die Behauptung gilt. Nach Induktionsvoraussetzung existieren Straight-Line-Baumgrammatiken $G_i = (N_i, P_i, S_i)$ mit $\val(G_i) = t_i$ für $i =1,2$. Wir kombinieren die beiden Grammatiken zu einer neuen Baumgrammatik $G = (N, P, S)$. Dabei ist $N = \{S, S'\} \cup (N_1 \dcup N_2)$ wobei $S, S' \not\in N_1 \cup N_2$ zwei neue Nichtterminale sind und
\[ P = \{S \ra S'(S_1), S'(x) \ra f(x, S_2)\} \cup P_1 \cup P_2 \]
Das $G$ eine Straight-Line-Baumgrammatik die $t$ erzeugt ist, ist klar. \hfill$\Box$
\end{description}
\end{bew}

Wenn wir uns den Beweis anschauen, so stellen wir fest, dass die so konstruierten Grammatiken linear, produktiv und monadisch sind. Weitere Regeln benötigen wir nicht. Diese stellen lediglich Abkürzungen für Ableitungsfolgen dar. So ist die Regel $A \ra f(B, C)$ zum Beispiel eine Abkürzung für die Regeln $A \ra B'(C)$ und $B'(x) \ra f(B, x)$.

\

Zur Navigation in einem durch eine Straight-Line-Baumgrammatik komprimierten Baum wollen wir, ähnlich wie im für Wörter, einen Ableitungsbaum nutzen.

\begin{defin}[Ableitungsbaum]
Sei $G = (N, P, S)$ eine Straight-Line-Baum\-gramma\-tik. Der \emph{Ableitungsbaum} von $\val(G)$ ist ein planarer, beschrifteter Baum mit einer endlichen, nicht-leeren Knotenmenge $V_G \subseteq \N^*$ für den gilt:
\begin{itemize}
	\item Die Wurzel ist mit $S$ beschriftet.
	\item Jeder innere Knoten hat eine Beschriftung aus $N$ und jedes Blatt ist mit einem Symbol aus $\F_0$ beschriftet.
	\item Sei $u$ ein Knoten des Ableitungsbaumes und $A \in N$ seine Beschriftung.
		Ist $A$ ein Typ-1-Nichtterminal, so gibt es entweder eine Regel $A(x) \ra B(C(x))$ oder $A \ra B(C)$. In beiden Fällen haben wir eine linke Kante zu einem Knoten $\ell$ und eine rechte Kante zu einem Knoten $r$. $\ell$ ist dabei mit $B$ und $r$ ist mit $C$ beschriftet.
		Ist $A$ ein Typ-2-Nichtterminal, so gibt es drei mögliche Regeln. Im Falle $A \ra a$ hat $u$ eine Kante zu einem mit $a$ beschrifteten Knoten. Im Falle $A \ra f(x, B)$ oder $A \ra f(B,x)$ hat $u$ eine Kante zu einem mit $B$ beschrifteten Knoten.
\end {itemize}
Seien nun $u, v \in V_G$ Knoten des Ableitungsbaumes. Der \emph{kleinste gemeinsame Vorfahre} (LCA) von $u$ und $v$ ist der Knoten $x \in V_G$, so dass $u = x.i$ und $v = x.j$ für geeignete $i, j \in \N^*$ gilt.
\end{defin}

\begin{bsp}
Betrachten wir noch einmal die Straight-Line-Baumgrammatik $H_n$ aus Beispiel \ref{bsp:Hn}. Abbildung \ref{fig:slpDerivTree} auf Seite \pageref{fig:slpDerivTree} zeigte uns den Ableitungsbaum von $G_n$. In Abbildung \ref{fig:sltgDerivTree} sehen wir den Ableitungsbaum von $H_n$. Zum besseren Verständnis wurde in der Abbildung eine etwas abweichende Beschriftung für einige Knoten verwendet. Knoten die mit einem Typ-2-Nichtterminal $A$ beschriftet sind, haben im Ableitungsbaum bekanntlich genau ein Kind. Dieses ist abweichend mit dem Term $t$ beschriftet den wir aus der Regel $(A \ra t) \in P$ erhalten.

\begin{figure}[h]
\begin{center}
\begin{picture}(60,72)(0,-70)
\gasset{Nframe=n,AHnb=0,Nw=6,Nh=6}
\node(nB0)(39,0){$B_0$}
\node(nB1e)(54,-20){$B_1$}
\node(n6)(48,-28){\rput{55}(0,0){...}}
\node(n7)(60,-28){\rput{305}(0,0){...}}

\node(nB01)(24,-10){$B_0^1$}
\node[NLangle=180,NLdist=6](nA0)(24,-20){$A_0(y_1, B_1)$}
\node(n4)(15,-32){\rput{55}(0,0){...}}
\node(n5)(33,-32){\rput{305}(0,0){...}}

\node(nBn)(15,-42){\rput{0}(-0.15,0){$B_n$}}
\node(nBn1)(0,-52){$B_n^1$}
\node[NLangle=180,NLdist=6](nBn3)(0,-62){$A_n(y_1, B_n^3)$}
\node(n13)(0,-72){$c$}
\node(nBn2)(30,-62){$B_n^2$}
\node(n12)(30,-72){$a$}

\drawedge(nB0,nB01){}
\drawedge(nB01,nA0){}
\drawedge(nB0,nB1e){}
\drawedge(nB1e,n6){}
\drawedge(nB1e,n7){}
\drawedge(nA0,n4){}
\drawedge(nA0,n5){}
\drawedge[sxo=-1.5,exo=-1.5](n4,nBn){}
\drawedge(nBn,nBn2){}
\drawedge(nBn,nBn1){}
\drawedge(nBn1,nBn3){}
\drawedge(nBn2,n12){}
\drawedge(nBn3,n13){}
\end{picture}
\end{center}
\caption{Ableitungsbaum der Straight-Line-Baumgrammatik $H_n$}
\label{fig:sltgDerivTree}
\end{figure}
\end{bsp}

Bei der Traversierung im Ableitungsbaum von Straight-Line-Wortgrammatiken hatten wir vorberechnete Abbildungen für Links- und Rechtsableitungen benutzt. Wir mussten nur eine Regelform beachten. Diesen Ansatz wollen wir auch für Straight-Line-Baumgrammatiken verfolgen. Hier gibt es jedoch fünf verschiedene Formen von Regeln die wir betrachten müssen. Zudem ist nicht klar, was eine Links- und was eine Rechtsableitung ist. Es fällt jedoch auf, dass Typ-1-Regeln immer zwei Nichtterminale enthalten, während Typ-2-Regeln höchstens ein Nichtterminal enthalten. Wir nehmen daher in Typ-1-Regeln als linkes Symbol das äußere Nichtterminal und als rechtes Symbol das innere Nichtterminal. In Typ-2-Regeln gibt es nur ein Terminalsymbol als äußeres Symbol und ein Nichtterminal als inneres Symbol. Wir werden daher die Definitionen der Links- und Rechtsableitungen etwas abwandeln und nicht in einem Terminalsymbol, sondern in einem Typ-2-Nichtterminal enden lassen. Wir werden später sehen, warum dies vorteilhaft ist.

\begin{defin}
Sei $G = (N, P, S)$ eine Straight-Line-Baumgrammatik und $A \in N$ ein beliebiges Nichtterminal. Sei weiterhin $\veps$ die leere Folge. Wir erhalten aus der Definition der Regelmenge $P$ eine eindeutig Regel $A \ra t$. Wir definieren nun induktiv die Folge der \mbox{\emph{Linksableitungen} $L : N \ra N^*$} durch
\[
L(A) = \begin{cases}
	B \cdot L(B)	&	\textrm{falls } t = B(C) \textrm{ oder } t = B(C(x))	\\
	\veps			&	\textrm{sonst}
\end{cases}
\]
für $B, C \in N$. Sei nun $L(A) = [A_1, \ldots, A_n]$. Die Länge $H: N \ra \N$ einer Ableitungsfolge ist dann $H(A) = n$. Außerdem definieren wir $L_i(A)$ als das $i$-te Symbol der Folge $L(A)$ für $1 \leq i \leq H(A)$.

\

Auf duale Weise erhalten wir die Folge der \emph{Rechtsableitungen} $R: N \ra N^*$. Sie ist induktiv definiert durch
\[
R(A) = \begin{cases}
	C \cdot L(C)	&	\textrm{falls } t = B(C) \textrm{ oder } t = B(C(x))	\\
	\veps			&	\textrm{sonst}
\end{cases}
\]
für $B, C \in N$. Sei wieder $R(A) = [A_1, \ldots, A_n]$. Die Länge $W: N \ra \N$ einer Ableitungsfolge ist dann $W(A) = n$. Zusätzlich definieren wir $R_i(A)$ als das $i$-te Symbol der Folge $R(A)$ für $1 \leq i \leq W(A)$.
\end{defin}

Wir sehen wieder sofort, dass die Abbildungen $L$ und $R$ Platz $O(|P|^2)$ benötigen. Im Wortfall hatte die maximale Linksableitung uns zudem das erste Textsymbol geliefert. Im Baumfall können wir die Beschriftung der Wurzel des vom Nichtterminal $S$ erzeugten Baumes mit Hilfe der Abbildung $L$ ebenfalls berechnen. Sei dazu $L_{H(S)}(S) = B$. Aus der Definition von $L$ wird ersichtlich, dass $B$ ein Typ-2-Nichtterminal ist. Die zu $B$ gehörende Regel $B \ra t_B$ liefert dann die Wurzelbeschriftung. Ist $t_B = a$, so ist die Beschriftung $a$. Ist $t_B = f(x, C)$ oder $t_B = f(C, x)$ für ein beliebiges $C \in N$, so ist die Beschriftung $f$. Wir bezeichnen sie auch mit $\lab(B)$.

\section{Navigation}
Sei also im weiteren $G = (N, P, S)$ eine feste Straight-Line-Baumgrammatik. In einem Baum können wir nicht wie in Wörtern nach links und rechts navigieren. Wir haben hier die Möglichkeit zum linken oder rechten Sohn zu wechseln oder aber zum Vaterknoten zurückzukehren. Um dies zu erreichen, wollen wir wieder die Abbildungen $L$ und $R$ verwenden. Außerdem nutzen wir einen Stack $T$ über $N \times \N \times \{L, R, U\}$ mit dem wir unsere Position im Ableitungsbaum kodieren. Für $d \in \{L, R\}$ bedeutet das Tripel $\langle X, i, d\rangle$ wie schon vorher, dass wir im Ableitungsbaum vom Typ-1-Nichtterminal $X$ genau $i$ Schritte in Richtung $d$ gehen. Wir bezeichnen solche Tupel auch wieder als Links- \mbox{respektive} Rechtsketten. Die Richtung $d = U$ zeigt an, dass $X$ ein Typ-2-Nichtterminal ist und wir eine Typ-2-Regel anwenden können. Wir nennen solche Tupel auch U-Schritte und erlauben zudem für $i$ nur \mbox{den Wert $0$}. 

Sei im folgenden $T = [t_1, \ldots, t_n]$ ein Stack über $N \times \N \times \{L, R, U\}$ mit \mbox{$t_j = \langle X_j, i_j, d_j\rangle$}. Um ungültige Kodierungen zu verhindern, sind wieder Forderungen an den Aufbau des Stacks zu stellen. Folgende Aussagen müssen für einen Stack $T$ stets erfüllt sein:

{\renewcommand{\labelenumi}{(\roman{enumi})}
\begin{enumerate}
\item $X_1 = S$
\item $d_i = L \Ra d_{i+1} \not= L$ und $d_i = R \Ra d_{i+1} \not= R$
\item Der Stack beschreibt einen Pfad von der mit $S$ beschrifteten Wurzel hin zu einem mit $\lab(X_n)$ beschrifteten Knoten.
\end{enumerate}
}

Wie im Wortfall kann auf eine Linkskette nicht direkt eine weitere Linkskette folgen und auf Rechtskette nicht direkt eine Rechtskette. Auf einen U-Schritt kann jedoch beliebiges folgen. Für den Stack lassen sich zudem noch weitere Aussagen treffen. So folgt aus (iii), dass $d_n = U$ sein muss. Außerdem ist die Anzahl der aufeinander folgenden U-Schritte beschränkt, wie nachfolgendes Lemma zeigt.

\begin{lemma}\label{lem:noUg2}
Im Stack $T$ können höchstens zwei U-Schritte aufeinander folgen.
\end{lemma}

\begin{bew}
Angenommen es gibt in $T$ eine Folge mit mehr als zwei aufeinander folgenden U-Schritten. Sei also $\langle X_1, 0, U\rangle$ der Anfang dieser Folge. Da $X_1$ ein Typ-2-Nichtterminal ist, gibt es eine Regel $X_1(y) \ra f(X_2, y)$ oder $X_1(y) \ra f(y, X_2)$. Somit ist $\langle X_2, 0, U\rangle$ das nächste Element der Folge. Aus der Definition der erlaubten Regeln folgt zudem, dass $X_2$ ein Nichtterminal von Rang $0$ ist. Die zu $X_2$ gehörende Regel hat somit die Form $X_2 \ra c$. Da $c$ ein Terminalsymbol ist, können wir keine Typ-2-Regel mehr anwenden. Es gibt somit keine weitere Elemente mehr in der Folge. Entsprechend der Annahme müsste es jedoch noch mindestens einen weiteren U-Schritt geben. Damit folgt der Widerspruch der Annahme.\hfill$\Box$
\end{bew}

\begin{bsp}
Um die Funktionsweise des Stacks besser zu verstehen, wollen wir uns ein Beispiel anschauen. Betrachten wir den Baum $t = f(a, f(a, f(f(f(a, a), a), a)))$. Er kann durch die Straight-Line-Baumgrammatik $G_t$ mit den Regeln
\[ \begin{array}{lp{15mm}l}
	\vspace{4pt}A_0 \ra A_1(A_2)				&	&	A_4(x) \ra f(x, A_2)			\\
	\vspace{4pt}A_1(x) \ra A_3(A_4(x)) 		&	&	A_5(x) \ra A_6(A_4(x))		\\
	\vspace{4pt}A_2 \ra a							&	&	A_6(x) \ra A_7(A_7(x))		\\
	\vspace{4pt}A_3(x) \ra A_5(A_4(x))		&	&	A_7(x) \ra f(A_2, x)			\\
	\end{array}\]
erzeugt werden. Abbildung \ref{fig:longLeft} zeigt uns den Vergleich zwischen dem Baum $t$ und dessen Ableitungsbaum. Betrachten wir beispielsweise den Knoten $2.2 \in \dom(t)$. Er wird durch den Stack $[\langle A_0, 3, L\rangle, \langle A_5, 1, R\rangle, \langle A_4, 0, U\rangle]$ kodiert. Seine direkten Verwandten sind kodiert durch:
\begin{itemize}
\item der linke Sohn $[\langle A_0, 2, L\rangle, \langle A_3, 1, R\rangle, \langle A_4, 0, U\rangle]$
\item der rechte Sohn $[\langle A_0, 3, L\rangle, \langle A_5, 1, R\rangle, \langle A_4, 0, U\rangle, \langle A_2, 0, U\rangle]$
\item der Vater $[\langle A_0, 4, L\rangle, \langle A_6, 1, R\rangle, \langle A_7, 0, U\rangle]$
\end{itemize}

\begin{figure}[h]
\begin{center}
\begin{picture}(142,70)(0,-67)
\gasset{Nframe=n,AHnb=0,Nw=6,Nh=6}
\node(t0)(20,0){f}
\node(t1)(10,-10){a}
\node(t2)(30,-10){f}
\node(t2.1)(20,-20){a}
\node(t2.2)(40,-20){f}
\node(t2.2.1)(30,-30){f}
\node(t2.2.2)(50,-30){a}
\node(t2.2.1.1)(20,-40){f}
\node(t2.2.1.2)(40,-40){a}
\node(t2.2.1.1.1)(10,-50){a}
\node(t2.2.1.1.2)(30,-50){a}
\drawedge(t0,t1){}
\drawedge(t0,t2){}
\drawedge(t2,t2.1){}
\drawedge(t2,t2.2){}
\drawedge(t2.2,t2.2.1){}
\drawedge(t2.2,t2.2.2){}
\drawedge(t2.2.1,t2.2.1.1){}
\drawedge(t2.2.1,t2.2.1.2){}
\drawedge(t2.2.1.1,t2.2.1.1.1){}
\drawedge(t2.2.1.1,t2.2.1.1.2){}

\node(a0)(126.5,0){$A_0$}
\node(a1)(111,-10){$A_1$}
\node(a1.1)(96,-20){$A_3$}
\node(a1.1.1)(82,-30){$A_5$}
\node(a1.1.1.1)(70,-40){$A_6$}
\node(a1.1.1.1.1)(62,-50){$A_7$}
\node(a1.1.1.1.1.1)(62,-60){$f(A_2, x)$}
\node(a1.1.1.1.1.1.1)(62,-70){a}
\node(a1.1.1.1.2)(78,-50){$A_7$}
\node(a1.1.1.1.2.1)(78,-60){$f(A_2, x)$}
\node(a1.1.1.1.2.1.1)(78,-70){a}
\node(a1.1.1.2)(94,-40){$A_4$}
\node(a1.1.1.2.1)(94,-50){$f(x, A_2)$}
\node(a1.1.1.2.1.1)(94,-60){$a$}
\node(a1.1.2)(110,-30){$A_4$}
\node(a1.1.2.1)(110,-40){$f(x, A_2)$}
\node(a1.1.2.1.1)(110,-50){$a$}
\node(a1.2)(126,-20){$A_4$}
\node(a1.2.1)(126,-30){$f(x, A_2)$}
\node(a1.2.1.1)(126,-40){$a$}
\node(a2)(142,-10){$A_2$}
\node(a2.1)(142,-20){$a$}
\drawedge(a0,a1){}
\drawedge(a1,a1.1){}
\drawedge(a1.1,a1.1.1){}
\drawedge(a1.1.1,a1.1.1.1){}
\drawedge(a1.1.1.1,a1.1.1.1.1){}
\drawedge(a1.1.1.1.1,a1.1.1.1.1.1){}
\drawedge(a1.1.1.1.1.1,a1.1.1.1.1.1.1){}
\drawedge(a1.1.1.1,a1.1.1.1.2){}
\drawedge(a1.1.1.1.2,a1.1.1.1.2.1){}
\drawedge(a1.1.1.1.2.1,a1.1.1.1.2.1.1){}
\drawedge(a1.1.1,a1.1.1.2){}
\drawedge(a1.1.1.2,a1.1.1.2.1){}
\drawedge(a1.1.1.2.1,a1.1.1.2.1.1){}
\drawedge(a1.1,a1.1.2){}
\drawedge(a1.1.2,a1.1.2.1){}
\drawedge(a1.1.2.1,a1.1.2.1.1){}
\drawedge(a1,a1.2){}
\drawedge(a1.2,a1.2.1){}
\drawedge(a1.2.1,a1.2.1.1){}
\drawedge(a0,a2){}
\drawedge(a2,a2.1){}
\end{picture}
\end{center}
\caption{Graph des Baumes $t$ (links) und dessen Ableitungsbaum (rechts)}
\label{fig:longLeft}
\end{figure}
\end{bsp}

\subsection{Zu den Kinderknoten}
Sei also $T = [t_1, \ldots, t_n]$ mit $t_j = \langle X_j, i_j, d_j\rangle$. Um den nächsten Knoten zu finden, benötigen wir wieder den kleinsten gemeinsamen Vorfahren $X_v$ vom aktuellen Knoten und dem nächsten Knoten. Wir betrachten zuerst den Top-Stack $t_n$. Aus den Voraussetzungen wissen wir, dass $d_n = U$ und $i_n = 0$ sind. Die Navigation zu den Kinderknoten hängt also von der zu $X_n$ gehörenden Regel ab. Wir müssen somit drei Fälle unterscheiden.

\

Fall $X_n(x) \ra f(B, x)$: Zum linken Kind können wir navigieren, indem wir einfach dem Nichtterminal $B$ folgen. Die Beschriftung des linken Kindes ist dann gleich der Wurzelbeschriftung des durch $B$ erzeugten Teilbaums. Ist $B$ ein Typ-1-Nicht\-terminal, so fügen wir $\langle B, H(B), L\rangle$ und $\langle L_{H(B)}(B), 0, U\rangle$ zu $T$ hinzu. Ist $B$ ein Typ-2-Nichtterminal, so fügen wir nur $\langle B, 0, U\rangle$ zu $T$ hinzu. Abbildung \ref{fig:treeNaviLeftB} auf der nachfolgenden Seite zeigt den Fall noch einmal bildlich.

\begin{figure}[h]
\begin{center}
\begin{picture}(18,36)(0,-34)
\gasset{Nframe=n,AHnb=0,Nw=5,Nh=5}
\node(n0)(18,0){\rput{45}(0,0){...}}
\node(nXn)(8,-10){$X_n$}
\node(nB)(8,-20){$f(B, x)$}
\node[Nw=0](nBl)(0,-30){}
\node[Nw=0](nBr)(16,-30){}
\node[Nw=0,NLangle=0,NLdist=-1.2](ng)(0,-36){$g(...)$}

\drawedge(n0,nXn){}
\drawedge(nXn,nB){}
\drawedge[sxo=1.8](nB,nBl){}
\drawedge[sxo=-3.5](nB,nBr){}
\drawedge(nBr,nBl){}
\drawline(0,-30)(0,-34)
\end{picture}
\end{center}
\caption{Navigation zum linken Kind im Fall $X_n(x) \ra f(B, x)$}
\label{fig:treeNaviLeftB}
\end{figure}

\newpage
Das rechte Kind ist hier die Wurzel des von $x$ erzeugten Teilbaum. Da $x$ noch unbekannt ist, müssen wir diesen Knoten finden. Wir verwerfen $t_n$ und betrachten das nächste Stackelement $t_{n-1}$. Kann $d_{n-1} = U$ sein? Angenommen dies wäre der Fall, dann gäbe es eine Regel $X_{n-1}(y) \ra g(X_n, y)$ bzw.\, $X_{n-1}(y) \ra g(y, X_n)$ mit $g \in \F_2$. Damit wäre $\rank(X_n) = 0$, was einen Widerspruch darstellt. Wir müssen noch drei Unterfälle unterscheiden.

{\begin{description}
\setlength{\itemindent}{-35pt}
\item 	Fall $d_{n-1} = L, i_{n-1} > 1$: Wir sind durch eine bei $X_{n-1}$ startende Linkskette der Länge $i_{n-1}$ zu $X_n$ gelangt. Sei nun $k = i_{n-1}-1$. Leiten wir $X_{n-1}$ nur $k$-mal ab, so gelangen wir zum Knoten $X_v = L_k(X_{n-1})$. Nun gibt es in $P$ entweder eine Regel \mbox{$X_v \ra X_n(X_n')$} oder $X_v(y) \ra X_n(X_n'(y))$. In beiden Fällen ist unser gesuchtes $x$ also das rechte Kind von $X_v$. Die Beschriftung des rechten Kindes erhalten wir, indem wir die Wurzelbeschriftung des von $X_n'$ erzeugten Teilbaums ermitteln. Somit ersetzen wir $t_{n-1}$ durch $\langle X_{n-1}, k, L\rangle$ und fügen $\langle X_v, 1, R\rangle$ zum Stack hinzu. Ist nun $X_n'$ ein Typ-1-Nichtterminal, so fügen wir $\langle X_n', H(X_n'), L\rangle$ sowie $\langle L_{H(X_n')}(X_n'), 0, U\rangle$ zum Stack hinzu. Ist $X_n'$ ein Typ-2-Nichtterminal, so fügen wir nur $\langle X_n', 0, U\rangle$ zum Stack hinzu. In Abbildung \ref{fig:treeNaviRightLg1} wird der Fall bildlich dargestellt.

\begin{figure}[h]
\begin{center}
\begin{picture}(35,54)(0,-52)
\gasset{Nframe=n,AHnb=0,Nw=5,Nh=5}
\node(n0)(20,-0.66){\rput{326}(0,0){...}}
\node[Nw=9,Nmr=0](nXn-1)(35,-10.66){$X_{n-1}$}
\node(nXn-1r)(50,-20.66){\rput{326}(0,0){...}}
\node[Nw=6](nXv)(15,-24){$X_v$}
\node(nXn)(0,-34){$X_n$}
\node(nB)(0,-44){$f(B,x)$}
\node[Nw=0](nBl)(-8,-54){}
\node[Nw=0](nBr)(8,-54){}
\node(nXns)(30,-34){$X_n'$}
\node[Nw=0](nXnsl)(22,-44){}
\node[Nw=0](nXnsr)(38,-44){}

\drawedge(n0,nXn-1){}
\drawedge(nXn-1,nXn-1r){}
\drawedge[ELside=r](nXn-1,nXv){\small $k$}
\drawedge[ELside=r](nXv,nXn){\small 1}
\drawedge(nXn,nB){}
\drawedge[sxo=1.8](nB,nBl){}
\drawedge[sxo=-3.5](nB,nBr){}
\drawedge(nBl,nBr){}
\drawedge(nXv,nXns){\small 1}
\drawedge[sxo=1.8](nXns,nXnsl){}
\drawedge[sxo=-3.5](nXns,nXnsr){}
\drawedge(nXnsl,nXnsr){}
\end{picture}
\end{center}
\caption{Fall $d_{n-1} = L, i_{n-1} > 1$}
\label{fig:treeNaviRightLg1}
\end{figure}

\item	Fall $d_{n-1} = L, i_{n-1} = 1$: In diesem Fall leiten wir $X_{n-1}$ nur einmal ab und erhalten bereits $X_n$. Wie im vorherigen Fall gibt es eine Regel $X_{n-1} \ra X_n(X_n')$ beziehungs\-weise $X_{n-1}(y) \ra X_n(X_n'(y))$ und das rechte Kind von $X_{n-1}$ ist unser gesuchtes $x$. Ist $X_{n-1} = S$, so ersetzen wir $t_{n-1}$ durch $\langle S, 1, R\rangle$. Sei also nun $X_{n-1} \not= S$. Damit gibt es ein weiteres Stackelement $t_{n-2}$. Ist $d_{n-2} = U$, so ersetzen wir $t_{n-1}$ durch $\langle X_{n-1}, 1, R\rangle$. Anderenfalls ist $d_{n-2} = R$ und $t_{n-2}$ somit eine Rechtskette. Wir löschen $t_{n-1}$ und verlängern die Kette $t_{n-2}$ um einen Schritt nach rechts, d.\,h. wir ersetzen sie durch $\langle X_{n-2}, i_{n-2}+1, R\rangle$. In allen drei Fällen gelangen wir \mbox{zu $X_n'$}. Wie vorher fügen wir nun $\langle X_n', H(X_n'), L\rangle$ sowie $\langle L_{H(X_n')}(X_n'), 0, U\rangle$ respektive nur $\langle X_n', 0, U\rangle$ zum Stack hinzu falls $X_n'$ ein Typ-1- bzw.\, Typ-2-Nicht\-terminal ist. Abbildung \ref{fig:treeNaviRightLe1} auf der nächsten Seite zeigt den Fall in bildlicher Darstellung.

\begin{figure}[h]
\begin{center}
\begin{picture}(44,51)(0,-49)
\gasset{Nframe=n,AHnb=0,Nw=5,Nh=5}
\node(n0)(11,-0.33){\rput{30}(0,0){...}}
\node[Nw=7](nXn-2)(0,-7){$X_{n-2}$}
\node(nXn-2l)(-11,-13.66){\rput{30}(0,0){...}}
\node[Nw=8](nXn-1)(21,-21){$X_{n-1}$}
\node(nXn)(6,-31){$X_n$}
\node(nB)(6,-41){$f(B, x)$}
\node[Nw=0](nBl)(-2,-51){}
\node[Nw=0](nBr)(14,-51){}
\node(nXns)(36,-31){$X_n'$}
\node[Nw=0](nXnsl)(28,-41){}
\node[Nw=0](nXnsr)(44,-41){}

\drawedge(n0,nXn-2){}
\drawedge(nXn-2,nXn-2l){}
\drawedge(nXn-2,nXn-1){\small$i_{n-2}$}
\drawedge[ELside=r](nXn-1,nXn){\small 1}
\drawedge(nXn,nB){}
\drawedge(nXn-1,nXns){\small 1}
\drawedge[sxo=1.8](nB,nBl){}
\drawedge[sxo=-3.5](nB,nBr){}
\drawedge(nBl,nBr){}
\drawedge[sxo=1.8](nXns,nXnsl){}
\drawedge[sxo=-3.5](nXns,nXnsr){}
\drawedge(nXnsl,nXnsr){}
\end{picture}
\end{center}
\caption{Fall $d_{n-1} = L, i_{n-1} = 1$ mit Rechtskette $t_{n-2}$}
\label{fig:treeNaviRightLe1}
\end{figure}

\item	Fall $d_{n-1} = R$: Da $t_{n-1}$ eine Rechtskette ist, gibt es Regeln $X^j(y) \ra Z^{j+1}(X^{j+1}(y))$ mit $X^0 = X_{n-1}$ und $X^ {i_{n-1}} = X_n$ für $0 \leq j < i_{n-1}$. Das heißt das gesuchte $x$ ist auch im Knoten $X_{n-1}$ unbekannt. Kann $X_{n-1} = S$ sein? Nein, da $\rank(X_{n-1}) = 1$ ist. Wir können also $t_{n-1}$ löschen. Außerdem gibt es ein Stackelement $t_{n-2}$. Kann nun $d_{n-2} = U$ sein? Auch das ist nicht möglich, da in diesem Fall $X_{n-1}$ in der zu $X_{n-2}$ gehörenden Regel vorkommen müsste, also Rang 0 haben müsste. Somit muss $d_{n-2} = L$ sein. Wir argumentieren nun für $t_{n-2}$ analog wie in den vorherigen Fällen für $d_{n-1} = L$ je nach dem welchen Wert $i_{n-2}$ hat. Die Veränderungen am Stack führen wir dann ebenfalls analog durch. Wir können den Fall in Abbildung \ref{fig:treeNaviRightR} grafisch nachvollziehen.

\begin{figure}[h]
\begin{center}
\begin{picture}(48,50)(0,-47)
\gasset{Nframe=n,AHnb=0,Nw=5,Nh=5}
\node(n0)(6,-3){\rput{333}(0,0){...}}
\node[Nw=9](nXn-2)(20,-10){$X_{n-2}$}
\node[Nh=7](nXn-1)(0,-20){$X_{n-1}$}
\node(nXn-1s)(-10,-25){\rput{30}(0,0){...}}
\node(nXn)(20,-30){$X_n$}
\node(nB)(20,-40){$f(B, x)$}
\node[Nw=0](nBl)(12,-50){}
\node[Nw=0](nBr)(28,-50){}
\node(nXns)(40,-20){$X_n'$}
\node[Nw=0](nXnsl)(32,-30){}
\node[Nw=0](nXnsr)(48,-30){}

\drawedge(n0,nXn-2){}
\drawedge[ELside=r](nXn-2,nXn-1){\small 1}
\drawedge(nXn-1,nXn-1s){}
\drawedge[ELdist=0.75](nXn-1,nXn){\small$i_{n-1}$}
\drawedge(nXn,nB){}
\drawedge[sxo=1.8](nB,nBl){}
\drawedge[sxo=-3.5](nB,nBr){}
\drawedge(nBl,nBr){}
\drawedge(nXn-2,nXns){\small 1}
\drawedge[sxo=1.8](nXns,nXnsl){}
\drawedge[sxo=-3.5](nXns,nXnsr){}
\drawedge(nXnsl,nXnsr){}
\end{picture}
\end{center}
\caption{Fall $d_{n-1} = R$}
\label{fig:treeNaviRightR}
\end{figure}
\end{description}}

Fall $X_n(x) \ra f(x, B)$: Dieser Fall wird analog zum vorherigen Fall behandelt. Hier sind nur linkes und rechtes Kind vertauscht, ansonsten bleibt die Argumentation dieselbe.

\

Fall $X_n \ra a$: Der aktuelle Knoten ist ein Blatt und hat somit keine Kinder. Der Stack $T$ bleibt unverändert.

\subsection{Zum Vaterknoten}
Die Navigation zum Vaterknoten hängt nicht von der zu $X_n$ gehörenden Regel ab. Vielmehr müssen wir hier im Stack die obersten Stackelemente anschauen. Da grundsätzlich $d_n = U$ gilt, löschen wir zuerst $t_n$ und betrachten $t_{n-1}$. Ist $X_{n-1} = S$, so sind wir bereits in der Wurzel des Baumes. Es gibt somit keinen Vater und wir fügen $t_n$ wieder zum Stack hinzu. Sei also nun $X_{n-1} \not= S$.

{\begin{description}
\setlength{\itemindent}{-35pt}
\item Fall $d_{n-1} = U$: Der Vater ist $t_{n-1}$. Wir ändern also nichts mehr am Stack.

\item Fall $d_{n-1} = R, i_{n-1} > 1$: Wir haben eine bei $X_{n-1}$ startende Rechtskette der Länge $i_{n-1}$. Der LCA ist nun $X_v = L_k(X_{n-1})$ mit $k = i_{n-1} - 1$ und wir ersetzen im Stack $t_{n-1}$ durch $\langle X_{n-1}, k, R\rangle$. Nun gibt es eine Regel $X_v \ra X_n'(X_n)$ beziehungsweise $X_v(x) \ra X_n'(X_n(x))$. Wir sehen leicht, dass $X_n'$ einen Baum erzeugt der $X_n$ als Teilbaum enthält. Nun gibt es für $0 \leq j < W(X_n')$ Regeln $X^j(x) \ra Z^{j+1}(X^{j+1}(x))$ mit $X^0 = X_n'$ und $X^{W(X_n')} = X_{n+1}$. Somit ist $X_n$ in jedem $X^j$ ein Teilbaum für $0 \leq j \leq W(X_n')$, insbesondere also auch von $X_{n+1}$. Da nun $X_{n+1}$ ein Typ-2-Nichtterminal ist, gehört hierzu eine Regel $X_{n+1}(x) \ra f(x, B)$ beziehungsweise $X_{n+1}(x) \ra f(B, x)$. Damit ist also $X_{n+1}$ der Vaterknoten. Wir fügen $\langle X_v, 1, L\rangle$ zum Stack hinzu. Ist $X_n'$ ein Typ-1-Nichtterminal, wird wie üblich $\langle X_n', W(X_n'), R\rangle$ und $\langle X_{n+1}, 0, U\rangle$ auf den Stack geschoben. Anderenfalls fügen wir nur $\langle X_n', 0, U\rangle$ hinzu. Der Fall ist in Abbildung \ref{fig:treeNaviFatherR} bildlich dargestellt.

\begin{figure}[h]
\begin{center}
\begin{picture}(40,46)(0,-44)
\gasset{Nframe=n,AHnb=0,Nw=5,Nh=5}
\node(n0)(12,0){\rput{27}(0,0){...}}
\node[Nw=9](nXn-1)(0,-6){$X_{n-1}$}
\node(nXn-1l)(-12,-12){\rput{27}(0,0){...}}
\node[Nw=6,Nh=6](nXv)(20,-16){$X_v$}
\node(nXn)(40,-26){$X_n$}
\node(n5)(40,-36){$f(...)$}
\node[Nw=6,Nh=6](nXns)(0,-26){$X_n'$}
\node[Nw=10](nXn+1)(20,-36){$X_{n+1}$}
\node(n9)(-10,-31){\rput{27}(0,0){...}}
\node(n10)(20,-46){$g(...)$}

\drawedge(n0,nXn-1){}
\drawedge(nXn-1,nXn-1l){}
\drawedge(nXn-1,nXv){\small$k$}
\drawedge[ELside=r](nXv,nXns){\small 1}
\drawedge(nXns,n9){}
\drawedge[ELpos=60](nXns,nXn+1){\scriptsize$W(X_n')$}
\drawedge(nXn+1,n10){}
\drawedge(nXv,nXn){\small 1}
\drawedge(nXn,n5){}
\end{picture}
\caption{Navigation zum Vaterknoten im Fall $d_{n-1} = R$}
\label{fig:treeNaviFatherR}
\end{center}
\end{figure}
\vspace{-10pt}

\item Fall $d_{n-1} = R, i_{n-1} = 1$: Hier ist $X_{n-1}$ der LCA. Wir haben wie im vorherigen Fall eine Regel $X_{n-1} \ra X_n'(X_n)$ bzw.\, $X_{n-1}(x) \ra X_n'(X_n(x))$. Wir entfernen $t_{n-1}$ vom Stack und betrachten das nächste Stackelement $t_{n-2}$. Ist $d_{n-2} = U$, so fügen wir $\langle X_{n-1}, 1, L\rangle$ zum Stack hinzu. Ist $d_{n-2} = L$, so ersetzen wir $t_{n-2}$ durch $\langle X_{n-2}, k, L\rangle$ mit $k = i_{n-2}+1$. In beiden Fällen gelangen wir zu $X_n'$. Wir argumentieren wieder analog wie im vorherigen Fall und fügen $\langle X_n', W(X_n'), R\rangle$ sowie $\langle X_{n+1}, 0, U\rangle$ zum Stack hinzu, falls $X_n'$ ein Typ-1-Nichtterminal ist, oder nur $\langle X_n', 0, U\rangle$, falls $X_n'$ ein Typ-2-Nichtterminal ist.

\item Fall $d_{n-1} = L$: Da $t_{n-1}$ eine Linkskette ist, hat der von $X_{n-1}$ erzeugte Baum dieselbe Wurzelbeschriftung wie der von $X_n$ erzeugte Baum. Wir haben also den Vater noch nicht gefunden. Wir entfernen somit $t_{n-1}$ vom Stack und betrachten das nachfolgende Stackelement $t_{n-2}$.

Ist $d_{n-2} = U$, so haben wir den Vater gefunden, denn zu $X_{n-2}$ gehört eine Regel $X_{n-2}(x) \ra f(x, X_{n-1})$ bzw.\, $X_{n-2}(x) \ra f(X_{n-1}, x)$. Dies ist auch nochmal im linken Teil von Abbildung \ref{fig:treeNaviFatherL} grafisch dargestellt.

Sei jetzt also $d_{n-2} = R$. Es gibt somit ein Nichtterminal $X_v$ mit einer dazu gehörigen Regel $X_v \ra X_{n-1}'(X_{n-1})$ bzw.\, $X_v(x) \ra X_{n-1}'(X_{n-1}(x))$. Wir erreichen es in Abhängigkeit vom Wert $i_{n-2}$.
Ist $i_{n-2} > 1$, dann ist $X_v = L_k(X_{n-2})$ mit $k = i_{n-2}-1$ und wir ersetzen $t_{n-2}$ durch $\langle X_{n-2}, k, R\rangle$.
Anderenfalls ist $i_{n-2} = 1$ und wir erhalten den LCA $X_v = X_{n-2}$. Ist jetzt $X_{n-2} = S$, so ersetzen wir $t_{n-2}$ durch $(S, 1, L)$. Ist $X_{n-2} \not= S$, dann löschen wir $t_{n-2}$ vom Stack. Außerdem gibt es ein weiteres Stackelement $t_{n-3}$. 
Ist $d_{n-3} = U$, so fügen wir $\langle X_{n-2}, 1, L\rangle$ zum Stack hinzu. 
Ist $d_{n-3} = L$, so ersetzen wir $t_{n-3}$ durch $\langle X_{n-3}, i_{n-3}+1, L\rangle$.
In allen Fälle landen wir jetzt beim Nichtterminal $X_{n-1}'$. Wie in den beiden vorherigen Fällen mit $d_{n-1} = R$ leiten wir jetzt von $X_{n-1}'$ aus maximal nach rechts zum Nichtterminal $X_{n+1}$ ab. Dort finden wir dann wieder den Vater. Ist also $X_{n-1}'$ ein Typ-1-Nichtterminal, so fügen wir $\langle X_n', W(X_n'), R\rangle$ und $\langle X_{n+1}, 0, U\rangle$ zum Stack hinzu. Anderenfalls schieben wir wie gehabt nur $\langle X_{n-1}', 0, U\rangle$ auf den Stack. Der rechte Teil der Abbildung \ref{fig:treeNaviFatherL} zeigt diesen Fall bildlich.

\begin{figure}[h]
\begin{center}
\begin{picture}(97,52)(0,-50)
\gasset{Nframe=n,AHnb=0,Nw=5,Nh=5}
\node(nXn-2)(20,0){$X_{n-2}$}
\node(nXn-1)(20,-10){$f(x, X_{n-1})$}
\node(nXn)(0,-30){$X_n$}
\node(nf)(0,-40){$f(...)$}
\node(nXn-1s)(30,-20){\rput{320}(0,0){...}}

\drawedge(nXn-2,nXn-1){}
\drawedge(nXn-1,nXn-1s){}
\drawedge[ELside=r,ELdist=.75](nXn-1,nXn){\small$i_{n-1}$}
\drawedge(nXn,nf){}


\node[Nw=10,Nmr=0](mXn-2)(63,0){$X_{n-2}$}
\node(mXn-2l)(54.5,-5){\rput{30}(0,0){...}}
\node[Nw=6](mXv)(80,-10){$X_v$}
\node(mXn-1s)(63,-20){$X_{n-1}'$}
\node(mXn-1sl)(54.5,-25){\rput{30}(0,0){...}}
\node[Nw=7](n6)(72,-40){$X_{n+1}$}
\node[Nw=0,NLangle=0,NLdist=-1.2](n7)(72,-50){$g(...)$}
\node[Nw=8,Nmr=0](mXn-1)(97,-20){$X_{n-1}$}
\node(n10)(88,-40){$X_n$}
\node[Nw=0,NLangle=0,NLdist=-1.2](n13)(88,-50){$f(...)$}
\node(n15)(105.5,-25){\rput{330}(0,0){...}}

\drawedge(mXn-2,mXn-2l){}
\drawedge(mXn-2,mXv){\small$k$}
\drawedge[ELside=r](mXv,mXn-1s){\small 1}
\drawedge(mXn-1s,mXn-1sl){}
\drawedge[ELside=r](mXn-1s,n6){\scriptsize$W(X_{n-1}')$}
\drawedge(n6,n7){}
\drawedge(mXv,mXn-1){\small 1}
\drawedge(mXn-1,n10){\small$i_{n-1}$}
\drawedge(n10,n13){}
\drawedge(mXn-1,n15){}
\end{picture}
\caption{Navigation zum Vaterknoten im Fall $d_{n-1} = L$}
\label{fig:treeNaviFatherL}
\end{center}
\end{figure}
\end{description}}

\begin{satz}\label{satz:treeNaviAlg}
Es gibt ein Algorithmus mit dem wir in einem durch eine Straight-Line-Baumgrammatik $G = (N, P, S)$ komprimierten Baum in konstanter Zeit pro Knoten und Platz $O(|P|^2)$ navigieren können.
\end{satz}
\newpage
\begin{bew}
Sei $G = (N, P, S)$ eine Straight-Line-Baumgrammatik. Wir berechnen zuerst im Preprocessing aus $G$ die Abbildungen $L$ und $R$ für die Links- und Rechtsableitungen. Diese benötigen den Platz $O(|P|^2)$. Anschließend initialisieren wir den Stack auf die Wurzel des Baumes, das heißt 
\[	T = [\langle S, H(S), L\rangle, \langle L_{H(S)}(S), 0, U\rangle]	\]
Nun verarbeiten wir die eingegebenen Navigationsanweisungen gemäß der in Kapitel 4.2 vorgestellten Weise. Wir nehmen hier nur konstant viele Ersetzungen durch, das heißt der Zeitbedarf um den nächsten Knoten zu erhalten beträgt $O(1)$. \hfill$\Box$
\end{bew}


%==================================================================================%


\chapter{Implementierung, Extras und Ausblick}
\section{Implementationsdetails}
Die Algorithmen sowie alle verwendeten Hilfsklassen wurde in Java 7 implementiert. Das Programm, der Quelltext und die Dokumentation sind online verfügbar unter
\begin{center}
\texttt{https://code.google.com/p/traversal-wt/}
\end{center}
Sie sollten auf allen Betriebssystemen, auf denen Java verfügbar ist, funktionieren. Dennoch sollten sie nur als Alphaversionen betrachtet werden. Weitere Informationen bezüglich Aufruf und Details zur Programmierung sind in der Programmdokumentation zu finden.

\section{Ableitungsfolgen in linearem Platz}
Betrachten wir noch einmal den Traversierungsalgorithmus für Wörter auf Seite \pageref{algo:wordTraverse}. Sei $G = (N, P, S)$ eine Straight-Line-Wortgrammatik und sei $L : N \ra N^* \cdot \Sigma$ die dafür definierte Abbildung für die Folge der Linksableitungen. Wenn wir uns Ableitungsfolgen anschauen, so stellen wir für eine Regel $A \ra BC$ fest, dass $L(B) = [L_2(A), \ldots, L_{H(A)}(A)]$ ist. Wir speichern somit Informationen mehrmals ab, was zu einem quadratischen Platzbedarf führt.

\

G\k{a}sieniec, Kolpakov, Potapov und Sant stellen in \cite{RTGrammarComp} einen Weg vor womit wir den Speicherplatzbedarf für die Folge der Linksableitungen auf $O(|P|)$ reduzieren können. Sie definieren für jedes Nichtterminal $A_0$ die Folge $L^R(A_0)$ als die rückwärts geschriebene Folge $L(A_0)$. Außerdem ist für $A_0$ das am weitesten links stehende Symbol $a \in \Sigma$ im von $A_0$ erzeugten Wort eindeutig definiert. Wir können also alle Nichtterminale in Äquivalenzklassen bezüglich $a$ partitionieren. Anschließend wird für jede Äquivalenzklasse $a$ ein Baum berechnet, mit dem die Folgen $L^R$ repräsentiert werden. Da nun jedes Nichtterminal in genau einem Baum vorkommt, haben alle Bäume zusammen höchstens $|N|$ viele Knoten, der Speicherbedarf beträgt also $O(|P|)$.

\begin{defin}
Seien $u$ und $v$ Knoten des Ableitungsbaumes, so dass $u$ ein Vorfahre von $v$ ist. Der \emph{Next-Link} von $u$ nach $v$ ist ein Kind $x$ von $u$, so dass auch $x$ ein Vorfahre von $v$ ist.
\end{defin}

Um im Ableitungsbaum in konstanter Zeit von $L_i(F)$ zu $L_{i-1}(F)$ für ein Nichtterminal $F$ zu traversieren, müssen somit wir das sogenannte Next-Link-Problem in konstanter Zeit lösen.  G\k{a}sieniec et.\, al.\, adaptieren dafür den LCA-Algorithmus von Schieber und Vizhkin. Letztere hatten in \cite{LCAAlgo} gezeigt, dass wir mit einem Preprocessing in linearer Zeit und linearem Platz  das Next-Link-Problem in konstanter Zeit lösen können. Damit lässt sich also die Traversierung in konstanter Zeit pro Symbol lösen.

\

Auf dieselbe Art und Weise können wir dies auch für die Folge der Rechtsableitungen machen. Damit lässt sich also auch die Navigation im Text in linearem Platz bewerkstelligen. Außerdem: Die Definitionen für Links- und Rechtsableitungen für Straight-Line-Baumgrammatiken waren auf eine sehr ähnliche Art definiert. Folglich lassen sich die Datenstrukturen auch hier nutzen, um den Speicherplatzbedarf zu reduzieren.


\section{Erweiterung der Straight-Line-Baumgrammatiken}
Zu Beginn des vierten Kapitels hatten wir uns auf Straight-Line-Baumgrammatiken eingeschränkt, die linear und monadisch waren. Lohrey, Maneth und Schmidt-Schauß zeigen in \cite{ParRed} ein konstruktives Verfahren mit dem man aus einer linearen, $k$-beschränkten Straight-Line-Baumgrammatik in Zeit $O(k \cdot r \cdot |G|)$ eine lineare, produktive und monadische Straight-Line-Baumgrammatik der Größe $O(r \cdot |G|)$ berechnen kann. Dabei ist $r$ der maximale Rang eines Symbols aus dem Rangalphabet $\F$ und $|G| = \sum_{A\ra t}|t|$.  

\

Außerdem haben wir das Rangalphabet auf Konstanten und binäre Symbole eingeschränkt. Lassen wir also schließlich im Rangalphabet $\F$ auch Terminalsymbole von beliebigem Rang zu, dann können wir nicht mehr von einem linken oder rechten Sohn sprechen, sondern nunmehr von Sohn $1$ bis Sohn $n$. Betrachten wir also die möglichen Formen von Regeln. An Typ-1-Regeln haben wir weiterhin nur $A \ra B(C)$ und \mbox{$A(x) \ra B(C(x))$} für Nichtterminale $B, C$. Typ-2-Regeln haben nun entweder wie bekannt die Form $A \ra a$ mit $a \in \F_0$ oder aber die Form $A(x) \ra f(B_1, \ldots, B_{i-1}, x, B_{i+1}, \ldots, B_n)$ mit $f \in \F_n$, \mbox{$1 \leq i \leq n$} und Nichtterminalen $B_j$ für alle $1 \leq j \leq n$. Wie vorher können wir mit dieser Regelmenge alle Bäume über $\F$ erzeugen. Dazu müssen wir das Lemma \ref{lemma:createsAll} neu beweisen. 

\begin{lemma}\label{lemma:createsAllArb}
Lemma \ref{lemma:createsAll} gilt auch für Rangalphabete mit Terminalsymbolen von beliebigem Rang.
\end{lemma}

\begin{bew}
Der Beweis geht bis zum Induktionsschritt analog. Sei also $t = f(t_1, \ldots, t_n)$ wobei $f \in \F_n$ ein beliebiges Terminalsymbol ist und $t_1, \ldots, t_n$ Bäume sind. Nach Induktionsvoraussetzung existieren Straight-Line-Baumgrammatiken $G_i = (N_i, P_i, S_i)$ mit $\val(G_i) = t_i$ für \mbox{$1 \leq i \leq n$}. Wir konstruieren uns eine Straight-Line-Baumgrammatik $G = (N, P, S)$. Die \mbox{Menge} der Nichtterminale ist $N = \{S, S'\} \cup \bigcup_i^n N_i$. Die Regelmenge $P$ enthält die Regeln
\begin{itemize}
\item $S \ra S'(S_1)$,
\item $S'(x) \ra f(x, S_2, \ldots, S_n)$ sowie
\item alle Regeln aus $P_i$ für $1 \leq i \leq n$,
\end{itemize}
Dabei sind $S, S' \not \in \bigcup_i^n P_i$. Nun gilt $\val(G) = t$.\hfill$\Box$
\end{bew}

Die Navigation zum Vaterknoten bleibt dieselbe. Da Knoten nun jedoch beliebig viele Kinder haben können, müssen wir im Navigationsalgorithmus für Bäume die Navigation zu den Kinderknoten modifizieren. Diese Anpassungen sind jedoch leicht zu bewerkstelligen. Sei also $T = [t_1, \ldots, t_n]$ der Stack aus dem Navigationsalgorithmus für Bäume mit $t_j = \langle X_j, i_j, d_j\rangle$. Die Navigation zu den Kinderknoten hing von der zu $X_n$ gehörenden Regel ab. Für Regeln der Form $X_n \ra a$ ändert sich nichts, hier sind weiterhin keine Kinder vorhanden. Sei also die zu $X_n$ gehörende Regel jetzt in der Form $X_n(x) \ra f(B_1, \ldots, B_{i-1}, x, B_{i+1}, \ldots, B_n)$ mit $f \in \F_n,  1 \leq i \leq n$ und $B_j \in N$ für alle $1 \leq j \leq n$. Für die Navigation zum $j$-ten Kind müssen wir zwei Fälle unterscheiden.

{\begin{description}
\setlength{\itemindent}{-35pt}
\item Fall $j \not= i$: Die Wurzel des $j$-ten Kindes ist die Wurzel des von $B_j$ erzeugten Teilbaumes. Folglich fügen wir $\langle B_j, H(B_j), L\rangle$ und $\langle L_{H(B_j)}(B_j), 0, U\rangle$ zum Stack hinzu, falls $B_j$ ein Typ-1-Nichtterminal ist. Anderenfalls fügen wir nur $\langle B_j, 0, U\rangle$ zu $T$ hinzu.

\item Fall $j = i$: Die Wurzel ist in diesem Fall die Wurzel des vom, noch unbekannten, $x$ erzeugten Teilbaumes. Wir finden sie auf dieselbe Art und Weise wie vorher. Auch die Anpassungen am Stack sind diesselben.
\end{description}}

\section{Preorder-Nummern}
Wir können während der Navigation durch einen Baum $t$ auch die Preorder-Nummer eines Knoten $v \in \dom(t)$ mitberechnen. Dazu müssen wir den Algorithmus etwas erweitern. Der Zeitbedarf bIeibt bei $O(1)$ pro Knoten. Zuerst benötigen wir jedoch ein paar Definitionen.

\begin{defin}[Teilbaum]
Sei $t = (\dom(t), \lambda_t)$ ein Baum und $v \in \dom(t)$ ein Knoten von $t$. Mit $t_{|v}$ bezeichnen wir den \emph{Teilbaum} von $t$, der $v$ als Wurzel hat.
\end{defin}

Wir sehen, dass $t_{|\veps} = t$ ist. Außerdem ist leicht ersichtlich, dass die Größe eines Teilbaumes gleich der Summe der Größen aller Kinder ist plus 1 für die Wurzel. Es gilt also $|t_{|v}| = 1 + \sum_{i=1}^n|t_{|v.i}|$ mit $n = \rank(\lambda_t(v))$ (Summenregel).

\begin{defin}[Preorder-Nummer]
Sei $t$ ein Baum und $v$ ein Knoten von $t$. Sei außer\-dem $1 \leq i \leq \rank(\lambda_t(v))$. Die \emph{Preorder-Nummer} von $v.i$ ist induktiv definiert durch $\pre(\veps) = 0$ und 
\[	\pre(v.i) = 1 + \pre(v) + \sum_{j=1}^{i-1} |t_{|v.j}|	\]
\end{defin}

\begin{bsp}
Sei $G$ die Grammatik aus Beispiel \ref{bsp:tree} und $t = \val(G)$. Es ist zum Beispiel $t_{|1} = f(a, a)$ und $t_{|3.1} = h(a)$. Abbildung \ref{fig:bspPreorder} zeigt die Preorder-Nummern der Knoten von $t$. Sie sind als Hochindex an die Knotenbeschriftung angefügt.

\begin{figure}[h]
\begin{center}
\begin{picture}(38,36)(0,-34)
\gasset{Nframe=n,AHnb=0,Nw=5,Nh=5}
\node(nveps)(16,0){$g^{0}$}
\node(n1)(4,-12){$f^{1}$}
\node(n2)(16,-12){$a^{4}$}
\node(n3)(28,-12){$f^{5}$}
\node(n11)(0,-24){$a^{2}$}
\node(n12)(8,-24){$a^{3}$}
\node(n31)(22,-24){$h^{6}$}
\node(n311)(22,-36){$a^{7}$}
\node(n32)(34,-24){$f^{8}$}
\node(n321)(30,-36){$a^{9}$}
\node(n322)(38,-36){$a^{10}$}

\drawedge(nveps,n1){}
\drawedge(nveps,n2){}
\drawedge(nveps,n3){}
\drawedge(n1,n11){}
\drawedge(n1,n12){}
\drawedge(n3,n31){}
\drawedge(n3,n32){}
\drawedge(n31,n311){}
\drawedge(n32,n321){}
\drawedge(n32,n322){}
\end{picture}
\end{center}
\caption{Beispiel \ref{bsp:tree} mit Preorder-Nummern}
\label{fig:bspPreorder}
\end{figure}
\end{bsp}

Um eine Preorder-Nummer eines Knotens zu berechnen, müssen wir also auch die Größe eines Teilbaumes berechnen können. Eine komplette Berechnung eines Teilbaums während eines Navigationsschritt würde jedoch nicht in konstanter Zeit möglich sein. Wir benötigen also eine andere Methode. Wir wissen, dass jeder Teilbaum aus einem Nichtterminal erzeugt wird. Folglich können wir für jedes Nichtterminal $A$ also während des Preprocessings der Regeln ermitteln welche Größe der von $A$ erzeugte Baum hat und speichern diese in einer Größentabelle. 

\begin{defin}[Größentabelle]
Sei $G = (N, P, S)$ eine Straight-Line-Baumgrammatik. Um die Größe $\|\cdot\| :  N \ra \N$ des Nichtterminals $A \in N$ zu berechnen, müssen wir die zu $A$ gehörende Regel betrachten. Daraus ergibt sich die folgende Definition:
\[	\|A\| = \begin{cases}
	\|B\| + \|C\|															&	\textrm{falls } A \ra B(C(x)) \textrm{ oder } A \ra B(C)																\\
	1																				&	\textrm{falls } A \ra a 																	\\
	1 + \smashoperator{\sum_{j \in \N[n,i]}}\|B_j\|		&	\textrm{falls } A \ra f(B_1, \ldots, B_{i-1}, x, B_{i+1}, \ldots, B_n)	\\
	\end{cases}\]
wobei $a \in \F_0, f \in \F_n$ und $B, C, B_1, \ldots, B_{i-1}, B_{i+1}, \ldots, B_n$ beliebige Nichtterminale sind. Außerdem ist $\N[n,i]$ die Menge aller natürlichen Zahlen von $1$ bis $n$ außer der Zahl $i$ ist. 
\end{defin}

Die Berechnung der \emph{Größentabelle der Nichtterminale} kann unter Nutzung der dynamischen Programmierung in polynomieller Zeit geschehen (siehe auch \cite{ParRed}).

\begin{bsp}\label{bsp:preorder}
Sei $t$ noch einmal der Baum aus Beispiel \ref{bsp:tree}. Wir hatten im Beispiel \ref{bsp:treeSlg} eine nicht-lineare Straight-Line-Baumgrammatik angegeben. Der Baum $t$ kann aber nach Lemma \ref{lemma:createsAllArb} auch einer linearen Straight-Line-Baumgrammatik erzeugt werden. Diese sei durch folgende Regeln gegeben:
\[\begin{array}{lp{12mm}lp{12mm}l}
	\vspace{4pt}A_0 \ra A_1(A_2)				&	&	A_4(x) \ra f(x, A_2)			&	&	A_8 \ra A_9(A_2)		\\
	\vspace{4pt}A_1(x) \ra A_3(A_4(x))		&	&	A_5(x) \ra g(A_7, A_2, x)	&	&	A_9(x) \ra h(x)			\\
	\vspace{4pt}A_2 \ra a							&	&	A_6(x) \ra f(A_8, x)			\\
	\vspace{4pt}A_3(x) \ra A_5(A_6(x))		&	&	A_7 \ra A_4(A_2)				\\
\end{array}\]

\newpage
Die Größentabelle sieht dann wie folgt aus:
\begin{figure}[h]
\[\begin{array}{l|c|c|c|c|c|c|c|c|c|c}
	A \in N		&	A_0	&	A_1	&	A_2	&	A_3	&	A_4	&	A_5	&	A_6	&	A_7	&	A_8	&	A_9	\\
	\hline
	\|A\|			&	11		&	10		&	1		&	8		&	2		&	5		&	3		&	3		&	2		&	1		\\
\end{array}\]
\caption{Größentabelle von Beispiel \ref{bsp:preorder}}
\end{figure}
\end{bsp}

Wir können nun die Preorder-Nummer während der Navigation berechnen. Dazu müssen wir den Navigationsalgorithmus \ref{satz:treeNaviAlg} leicht anpassen. Während des Preprocessing berechnen wir zusätzlich die Größentabelle der Nichtterminale. Zudem merken wir uns im Stack in den U-Schritten die Größe des Teilbaumes der sich unter dem in $T$ kodierten Knoten befindet. Beim Initialisieren des Stacks müssen wir also noch die Größe des gesamtes Baumes notieren. Wir initialisieren somit den Stack stattdessen mit dem Wert \mbox{$T = [\langle S, H(S), L\rangle, \langle L_{H(S)}(S), \|S\|, U\rangle]$}.

\subsection*{Preorder-Nummer der Kinder}
Sei also $G = (N, P, S)$ eine Straight-Line-Baumgrammatik und $T = [t_1, \ldots, t_n]$ der Stack aus dem Navigationsalgorithmus für Bäume mit $t_j = \langle X_j, i_j, d_j\rangle$. Sei außerdem $p$ die Preorder-Nummer des aktuellen Knotens $v$ und $s$ die Größe des Teilbaumes $t_{|v}$.  Um zum $k$-ten Sohn zu navigieren, mussten wir die zu $X_n$ gehörende Regel betrachten.

{\begin{description}
\setlength{\itemindent}{-35pt}
\item Fall $X_n \ra a$: Wir befinden uns in einem Blatt. Somit gibt es keine Kinder und wir müssen keine neue Preorder-Nummer berechnen.

\item Fall $X_n(x) \ra f(B_1, \ldots, B_{i-1}, x, B_{i+1}, \ldots, B_n)$ mit $f \in \F_n$ und $1 \leq i \leq n$: Wir berechnen zuerst die Größen der Nichtterminale $B_1, \ldots, B_{i-1}, B_{i+1}, \ldots, B_n$ mit Hilfe der Größentabelle. Weil das Nichtterminal $B_j$ den Teilbaum $t_{|v.j}$ erzeugt, gilt somit $\|B_j\| = |t_{|v.j}|$. Da wir auch die Größe des aktuellen Teilbaumes kennen, können wir damit auch die Größe des $i$-ten Sohnes berechnen, denn es gilt bekanntlich
\[		s = |t_{|v}| = 1 + \sum_{i=1}^n|t_{|v.i}| = 1 + |t_{|v.i}| + \smashoperator{\sum_{j \in \N[n,i]}}\|B_j\|	\]
Durch umstellen erhalten wir also den Wert von $|t_{|v.i}|$. Zur Vereinfachung der Schreibweise schreiben wir $|t_{|v.i} =: \|B_i\|$. Die Preorder-Nummer des $k$-ten Sohnes erhalten wir nun über
\[	\begin{array}{lcl}
	\pre(v.k)	&	=	&	1 + \pre(v) + \smashoperator{\sum_{j=1}^{k-1}}|t_{|v.j}|	\\
					&	=	&	1 + p + \smashoperator{\sum_{j=1}^{k-1}}\|B_j\|				\\
	\end{array}	\]
Nun suchen wir mit Hilfe des Navigationsalgorithmus den $k$-ten Sohn von $v$ und passen den Stack $T$ entsprechend an. Abschließend müssen wir uns noch die Größe von $t_{|v.k}$ merken. Wir ersetzen also den Top-Stack $\langle X, 0, U\rangle$ durch $\langle X, |t_{|v.k}|, U\rangle$.

\end{description}}

\subsection*{Preorder-Nummer des Vaters}
Sei wieder $G = (N, P, S)$ eine Straight-Line-Baumgrammatik und $T = [t_1, \ldots, t_n]$ der Stack aus dem Navigationsalgorithmus für Bäume mit $t_j = \langle X_j, i_j, d_j\rangle$. Sei außerdem $p$ die Preorder-Nummer des aktuellen Knotens $v.k$ und $s$ die Größe des Teilbaumes $t_{|v.k}$. Mit Hilfe des Navigationsalgorithmus suchen wir den Vaterknoten. Aus der Navigation zu den Kindern haben wir gesehen, dass es zwei "`Arten"' von Kinder gibt. Zum einen Kinder die aus einem bekannten Nichtterminal der zugehörigen Regel entstehen. In diesem Fall haben wir zum Stack nur neue Elemente hinzugefügt. Zum anderen Kinder die aus der unbekannten Variable $x$ entstehen. Hier haben wir die obersten zwei, drei Stackelemente verworfen oder geändert und dann weitere Elemente auf den Stack gepusht. Bei der Navigation zum Vater treten diese beiden Arten wieder auf. Wir haben also zwei Fälle zu unterscheiden:

{\begin{description}
\setlength{\itemindent}{-35pt}
\item 	Wir finden im Navigationsalgorithmus den Vater in einem U-Schritt $\langle X, s, U\rangle$ im Stack: In diesem Fall ist die Größe des Vaters bekannt, genauer sie ist $s$. Außerdem können wir aus der zu $X$ gehörenden Regel $X \ra f(B_1, \ldots, B_{i-1}, x, B_{i+1}, \ldots, B_n)$ die Größen aller Kinder berechnen. Mit der Summenregel erhalten wir auch die Größe des unbekannten Kindes $x$. Der Einfachheit halber schreiben wir auch hier wieder $|t_{v.i}| =: \|B_i\|$. Wir können dann die neue Preorder-Nummer berechnen in dem wir die Gleichung 
\[	\pre(v.k) = 1 + \pre(v) + \smashoperator{\sum_{j=1}^{k-1}}|t_{|v.j}|	\]
nach $\pre(v)$ umstellen, also
\[ \begin{array}{lcl}
	\pre(v)	&	=	&	\pre(v.k) - 1 - \smashoperator{\sum_{j=1}^{k-1}}|t_{|v.j}|		\\
				&	=	&	p - 1 - \smashoperator{\sum_{j=1}^{k-1}}\|B_j\|					\\
	\end{array}	\]

\item 	Wir berechnen den Vater aus dem aktuellen Stack: Da wir keinen U-Schritt gefunden haben, ist die Größe des Vaters unbekannt. Wir können aber wie gewohnt aus der zugehörigen Regel die Größen aller Kinder berechnen. Insbesondere ist die Größe des unbekannten Kindes $x$ gleich der Größe von $t_{|v.k}$, also gleich $s$. Somit können wir auch die Größe des Vaters $s'$ berechnen. Die Berechnung der neuen Preorder-Nummer geht wieder wie im vorherigen Fall. Im Stack ersetzen wir aber den Top-Stack $\langle X_v, 0, U\rangle$ noch durch $\langle X, s', U\rangle$.
\end{description}}

\newpage
\section{Obergrenze für die Größe des Stacks}
Für die Navigationsalgorithmen haben wir einen Stack genutzt um Positionen im Ableitungsbaum zu kodieren. Da die Ableitungsrelation azyklisch ist, können wir als naive Obergrenze für die Größe des Stacks $T$ die Anzahl der Nichtterminale, also $|N|$, angeben. Der Stack ist so organisiert, dass es immer einen Wechsel zwischen Links- und Rechtsketten gibt. Folglich sind es auch diese Wechsel die die möglichen Werte des Stacks, und damit seiner Größe, beschränken.  Dies ermöglicht es uns eine genauere Grenze während des Preprocessings in polynomieller Zeit mitzuberechnen. Betrachten wir zuerst den \mbox{Navigationsalgorithmus} für Straight-Line-Wortgrammatiken.

\begin{defin}
Sei $G = (N, P, S)$ eine Straight-Line-Wortgrammatik über einem endlichen Alphabet $\Sigma$. Sei zudem $T$ der im Navigationsalgorithmus verwendete Stack. Die \emph{längste von links startende Links-Rechts-Kette} eines Nichtterminals $A \in N$ ist definiert durch
\[ \bl(A) = \begin{cases}
	1										&	\textrm{falls } A \ra ab \textrm{ oder } A \ra aC\\
	\max\{\bl(B),1+\br(B)\}	&	\textrm{falls } A \ra Ba \textrm{ oder } A \ra BC\\
	\end{cases}
\]
Analog definieren wie die \emph{längste von rechts startende Links-Rechts-Kette} eines Nichtterminals $A \in N$ durch
\[ \br(A) = \begin{cases}
	1										&	\textrm{falls } A \ra ab \textrm{ oder } A \ra Ba\\
	\max\{1+\bl(C),\br(C)\}	&	\textrm{falls } A \ra aC \textrm{ oder } A \ra BC\\
	\end{cases}
\]
Dabei sind $a, b \in \Sigma$ und $B, C \in N$.
\end{defin}

\begin{bsp}
Betrachten wir die Grammatik aus Beispiel \ref{bsp:slcfGrammar}.1. Wir erhalten folgende Werte für $\bl$ und $\br$:
\[	\begin{array}{l|lllllllll}
				&	A	&	B	&	C	&	D	&	E	&	F	&	G	&	H 	&	I 	\\
	\hline
	\bl 		&	1	&	2	&	2	&	3	&	4	&	4	&	5	&	5	&	5	\\
	\br		&	1	&	1	&	2	&	3	&	3	&	4	&	4	&	3	&	1	\\
	\end{array}\]
\end{bsp}

\begin{lemma}
Sei $G = (N, P, S)$ eine Straight-Line-Baumgrammatik. Die Größe des Stacks $T$ im Navigationsalgorithmus für Wörter ist beschränkt durch \[|T| \leq \max\{\bl(S), \br(S)\}\]
\end{lemma}

\begin{bew}
Wir müssen für alle möglichen Regeln des Startsymbols die Behauptung zeigen. Dazu seien $a, b \in \Sigma$ und $S', S_1, S_2 \in N$ beliebig.

\begin{enumerate}
\item $S \ra ab$: Der von $S$ erzeugte Baum hat das Aussehen $\tree_G(S) = S(a, b)$. Außerdem ist $\bl(S) = \br(S) = 1$. Der Stack $T$ kann nur $[\langle S, 1, L\rangle]$ und $[\langle S, 1, R\rangle]$ als mögliche Elemente haben, also gilt die Behauptung $|T| = 1 \leq \max\{\bl(S), \br(S)\} = 1$.

\item $S \ra aS'$: Der von $S$ erzeugte Baum hat das Aussehen $\tree_G(S) = S(a, S')$. Es ist $\bl(S) = 1$ und $\br(S) = \max\{1+\bl(S'), \br(S')\}$. Der Stack $T$ kann folgende Werte annehmen:
\begin{itemize}
	\item $[\langle S, 1, L\rangle]$, also $|T| = 1$
	\item $[\langle S, 1, R\rangle, \langle S', i, L\rangle, ...]$ mit $i  < H(S')$, also $|T| = 1 + \bl(S')$
	\item $[\langle S, i, R\rangle, \langle S'', k, L\rangle, ...]$ mit $i > 1, k < H(S'')$ und $S'' = R_k(S')$ für ein $k \in \N$, also $|T| = \br(S')$
\end{itemize}

Damit gilt:
\[\begin{array}{lcl}
	|T|	&	\leq	&	\max\{1, 1+\bl(S'), \br(S')\}				\\
			&	=		&	\max\{1, \max\{1+\bl(S'), \br(S')\}\}	\\
			&	=		&	\max\{\bl(S), \br(S)\}
	\end{array}\]

\item $S \ra S'a$: Dieser Fall geht analog zum vorherigen Fall.

\item $S \ra S_1S_2$: Der von $S$ erzeugte Baum hat hier die Form $\tree_G(S) = S(S_1, S_2)$. Zudem sind $\bl(S) = \max\{\bl(S_1), 1+\br(S_1)\}$ und $\br(S) = \max\{\bl(S_2)+1, \br(S_2)\}$. Der Stack $T$ kann folgende Formen haben:
\begin{itemize}
	\item $[\langle S, i, L\rangle, \langle S_1', j, R\rangle, ...]$ mit $i > 1, j < W(S_1')$ und $S_1' = L_k(S_1)$ für ein $k \in \N$, also $|T| = \bl(S_1)$
	\item $[\langle S, 1, L\rangle, \langle S_1, i, R\rangle, ...]$ mit $i < W(S_1)$, also $|T| = 1 + \br(S_1)$
	\item $[\langle S, 1, R\rangle, \langle S_2, i, L\rangle, ...]$ mit $i < H(S_2)$, also $|T| = 1 + \bl(S_2)$
	\item $[\langle S, i, R\rangle, \langle S_2', j, L\rangle, ...]$ mit $i > 1, j < H(S_2')$ und $S_2' = R_k(S_2)$ für ein $k \in \N$, also $|T| = \br(S_2)$
\end{itemize}

Damit gilt 
\[ \begin{array}{lcl}
	|T|	&	\leq	&	\max\{\bl(S_1), 1+\br(S_1), 1+\bl(S_2), \br(S_2)\}	\\
			&	=		&	\max\{\max\{\bl(S_1),1+\br(S_1)\}, \max\{1+\bl(S_2), \br(S_2)\}\}	\\
			&	=		&	\max\{\bl(S), \br(S)\}
	\end{array}
\]
\end{enumerate}\hfill$\Box$
\end{bew}

Die Berechnung von $\bl$ und $\br$ kann während des Preprocessings geschehen. Auch hier müssen wir unter Nutzung der dynamischen Programmierung jedes Nichtterminal nur einmal berechnen, die Laufzeit ist also linear. Für Straight-Line-Baumgrammatiken ist eine ähnliche Aussage möglich. Hier müssen wir beachten, dass Links- und Rechtsableitungen nur für Typ-1-Nichtterminale existieren. Für Typ-2-Nichtterminale haben wir nur die Möglichkeit des U-Schrittes. Wir müssen also die Definition der längsten Links-Rechts-Ketten anpassen.

\begin{defin}
Sei $G = (N, P, S)$ eine Straight-Line-Baumgrammatik über einem Rangalphabet $\F$. Sei weiterhin $T$ der im Navigationsalgorithmus für Bäume verwendete Stack. Die \emph{längste von links startende Links-Rechts-Kette} eines Nichtterminals $A \in N$ ist definiert durch
\[		B_L(A) := \max\{B_L(C), 1 + B_R(C)\}	\]
falls $A$ ein Typ-1-Nichtterminal ist und die zugehörige Regeln in der Form $A \ra C(D)$ oder $A(x) \ra C(D(x))$ ist, und
\[		B_L(A) := 1 + \max\{B_L(A_i), B_R(A_i) \mid i \in \N[n,i]\}	\]
falls $A$ ein Typ-2-Nichtterminal ist und $A(x) \ra f(B_1, \ldots, B_{i-1}, x, B_{i+1}, \ldots, B_n)$ die zugehörige Regel ist.

\

Analog definieren wie die \emph{längste von rechts startende Links-Rechts-Kette} eines Nichtterminals $A \in N$ durch
\[		B_R(A) := \max\{1+B_L(D),B_R(C)\}	\]
falls $A$ ein Typ-1-Nichtterminal ist und $A \ra C(D)$ oder $A(x) \ra C(D(x))$ die zugehörige Regel ist, und
\[		B_R(A) := 1 + \max\{B_L(A_i), B_R(A_i) \mid i \in \N[n,i]\}	\]
falls $A$ ein Typ-2-Nichtterminal ist und $A(x) \ra f(B_1, \ldots, B_{i-1}, x, B_{i+1}, \ldots, B_n)$ die zugehörige Regel ist.

\

In beiden Definitionen sind dabei $C, D, B_i \in N$ für alle $i \in \N[n,i]$ und $f \in \F_n$.
\end{defin}

\begin{lemma}
Die Größe von $T$ ist beschränkt durch $|T| \leq \max\{B_L(S), B_R(S)\}$.
\end{lemma}

\begin{bew}
Der Beweis funktioniert auf ähnliche Art und Weise wie der Beweis für Wortgrammatiken, wir müssen nur mehr Fälle betrachten. Er sei dem Leser überlassen.
\end{bew}

%==================================================================================%


\chapter*{Zusammenfassung}
Kontextfreie Grammatiken sind ein wichtiges Konzept bei der Komprimierung von Daten. Dies gilt sowohl für Wörter als auch für deren Verallgemeinerung der Bäume. Zu diesem Zweck nutzen wir sogenannte Straight-Line-Grammatiken. Diese erzeugen stets genau ein Wort beziehungsweise genau einen Baum. Wir haben uns zuerst die Definitionen für Wortgrammatiken angeschaut und dann mit Hilfe von Links- und Rechtsableitungen gezeigt, dass man in Echtzeit und nur quadratisch viel extra Platz durch den Text navigieren kann ohne ihn komplett zu dekomprimieren. Anschließend haben wir uns den Baumgrammatiken zugewendet und gezeigt, dass sich die Resultate für Wörter auch auf Bäume verallgemeinern lassen. Im letzten Kapitel haben wir uns noch ein Paar Erweiterungen und Zusatzresultaten zugewendet.


%==================================================================================%


\begin{thebibliography}{999}
\bibitem{CompressedSearchLZW}
	Amihood Amir, Gary Benson, Martin Farrach.
	\emph{Let sleeping files lie: Pattern Matching in Z-Compressed Files.}
	Proceedings of 5th Annual ACM-SIAM Symposium on Discrete Algorithms: 705-714,
	1994.

\bibitem{RunLength}
	Amihood Amir, Gad M. Landau, Dina Sokol.
	\emph{Inplace Run-Length 2d Compressed Search}.
	Proceedings of 11th Annual ACM-SIAM Symposium on Discrete Algorithms: 817-818,
	2000.

\bibitem{BPLEX}
	Giovanni Busatto, Markus Lohrey, Sebastian Maneth.
	\emph{Efficient memory representation of XML document trees}.
	Inf. Syst. 33(4-5): 456-474,
	2008.

\bibitem{PaperPPM}
	John Cleary, Ian Witten.
	\emph{Data Compression Using Adaptive Coding and Partial String Matching}.
	In: Communications, IEEE Transactions on. 32, Nr. 4: 396–402,
	1984.

\bibitem{TaTa}
	Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, Marc Tommasi.
	\emph{Tree Automata Techniques and Applications}.
	Online: \texttt{http://tata.gforge.inria.fr/},
	2007.

\bibitem{RTGrammarComp}
	Leszek G\k{a}sieniec, Roman Kolpakov, Igor Potapov, Paul Sant.
	\emph{Real-time traversal in grammar-based compressed files}.
	Data Compression Conference: 458,
	2005.

\bibitem{HuffmanCode}
	David Albert Huffman.
	\emph{A method for the construction of minimum-redundancy codes}.
	Proceedings of the I.R.E.: 1098-1101,
	1952.

\bibitem{RecursivePairing}
	N. Jesper Larsson, Alistair Moffat.
	\emph{Offline Dictionary-Based Compression}.
	Data Compression Conference: 296-305,
	1999.
	 
\bibitem{survey}
	Markus Lohrey, Sebastian Maneth.
	\emph{Algorithmics on SLP-compressed strings: a survey}.
	Groups Complexity Cryptology 4(2): 241-299,
	2012

\bibitem{treeXPath}
	Markus Lohrey, Sebastian Maneth.
	\emph{The complexity of tree automata and XPath on grammar-compressed trees}.
	Theoretical Computer Science 363(2): 196-210,
	2006.

\bibitem{ParRed}
	Markus Lohrey, Sebastian Maneth, Manfred Schmidt-Schauß.
	\emph{Parameter Reduction and Automata Evaluation for Grammar-Compressed Trees}.
	J. Comput. Syst. Sci. 78(5): 1651-1669,
	2012.

\bibitem{TreeRePairPaper}
	Markus Lohrey, Sebastian Maneth und Roy Mennicke.
	\emph{Tree Structure Compression with RePair}.
	Data Compression Conference: 353-362,
	2011.

\bibitem{TreeRePairImpl}
	Roy Mennicke.
	\emph{Re-pair for trees}.
	Diplomarbeit,
	Universität Leipzig,
	2010.

\bibitem{Sequitur}
	Craig Nevill-Manning, Ian Witten.
	\emph{Identifying hierarchical structure in sequences: A linear-time algorithm}.
	J. Artif. Intell. Res. (JAIR) 7: 67-82,
	1997.

\bibitem{CNF}
	Grzegorz Rozenberg, Arto Salomaa.
	\emph{Handbook of Formal Languages. Volume 1: Word, Language, Grammar}.
	Springer: 124-125,
	1997.

\bibitem{GeneralTrees}
	Grzegorz Rozenberg, Arto Salomaa.
	\emph{Handbook of Formal Languages. Volume 3: Beyond Words}.
	Springer: 1-68,
	1997.

\bibitem{LCAAlgo}
	Baruch Schieber, Uzi Vizhkin.
	\emph{On finding the lowest common ancestors: Simplification and Parallelization}.
	SIAM Journal on Computing 17 (6): 1253–1262,
	1988.

\bibitem{LZWelch}
	Terry A. Welch.
	\emph{A Technique for High-Performance Data Compression}.
	IEEE Computer 17(6): 8-19,
	1984.

\bibitem{LZ}
	Jacob Ziv, Abraham Lempel.
	\emph{Compression of Individual Sequences Via Variable-Rate Coding}.
	IEEE Transactions on Information Theory 24(5): 530-536,
	1978.
\end{thebibliography}

%==================================================================================%

\chapter*{Selbstständigkeitserklärung}
Ich versichere, dass ich die vorliegende Arbeit selbstständig verfasst habe. Dabei habe ich ausschließlich die im Literaturverzeichnis verwendeten Quellen und Hilfsmittel verwendet. Zitate sind als solche gekennzeichnet. Mir ist bewusst, dass eine Zuwiderhandlung auch nachträglich zur Aberkennung des Abschlusses führen kann.

\vspace{3cm}
\centering
\begin{tabular}{ccc}
\hspace{4cm}		&	\hspace{2cm} 	&	\hspace{4cm}	\\
\cline{1-1}\cline{3-3}
Ort, Datum		&				&	Unterschrift	\\
\end{tabular}
\end{document}